海康威视-技术笔试-代码题-求解

看似很简单的一道二叉树逐层遍历，我用BFS求解，但是最后却Time Limit Exceed。求助下各位大佬，代码的问题在哪，以及如何优化。



以下是原题回忆：

(1) 给定二叉树的根节点root，返回其节点的层序遍历（也就是逐层，从左到右访问所有节点）。

(2) 输入数据为二叉树跟节点。None表示空节点，！表示结束构建，节点和节点通过空格间隔。

(3) 样例输入：3 9 20 None None 15 7 ！

(4) 样例输出：[[3]，[9，20]，[15，7]]。


以下是我的BFS代码：

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def build_tree(data):
    if not data or data[0] == 'None':
        return None
    data.pop()
    root = TreeNode(int(data[0]))
    # queue = [root]
    queue = deque([root])
    i = 1
    while queue and i < len(data):
        node = queue.popleft()
        if data[i] != 'None':
            node.left = TreeNode(int(data[i]))
            queue.append(node.left)
        i += 1
        if i >= len(data):
            break
        if data[i] != 'None':
            node.right = TreeNode(int(data[i]))
            queue.append(node.right)
        i += 1
    return root

def levelOrder(root):
    # base cases
    if not root:
        return []
    # bfs search
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        cur_level = []
        for i in range(level_size):
            node = queue.popleft()
            cur_level.append(int(node.val))
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(cur_level)
    # return res
    return res

input_data = input().split()
tree = build_tree(input_data)
print(levelOrder(tree))

# 样例输入：3 9 20 None None 15 7 ！
# 样例输出：[[3]，[9，20]，[15，7]

没米，看不见你的code。这题目很容易，按层遍历要用queue，你是不是忘记queue pop了？导致infinite loop

建一个list来存nodes，直接遍历原list， 如果item不为None，新建node并与其parent相连， 与parent的关系可以与位置相关，比如位置为3则其parent为（3-1）/2=1，3是1的左节点，类似4得到1.5，为1的右节点。 这样遍历一边，有数字建node，没数字记为None，O(n) time and space

补充内容 (2023-08-22 03:32 +08:00):
过多的append和pop很花时间