BFS 以每个顺序检索值的元素

Question

我试图解决二叉树级别顺序遍历问题 - LeetCode给定一棵二叉树，返回其节点值的层序遍历。（即从左到右，一层一层）。例如：给定二叉树[3,9,20,null,null,15,7]，    3   / \  9  20    /  \   15   7返回其层序遍历为：[  [3],  [9,20],  [15,7]]我的方案很直观，BFS遍历收集每一层的值from collections import dequeclass Solution:    def levelOrder(self, root):        if not root: return [] #base case         res = []        #queue to colloct all the nodes        queue = deque([root])         while queue:            level_vals = [] #hold the values at the current level.            for _ in range(len(queue)): #evalute once before execution enter the loop                cur = queue.popleft()                if node.left:                    queue.append(cur.left)                if node.right:                    queue.append(cur.right)                level_vals.append(cur.val)            res.append(level_vals)        return res 我在讨论区阅读了这样的 bfs 和队列解决方案# BFS + dequedef levelOrder(self, root):    res, queue = [], deque([(root, 0)])    while queue:        cur, level = queue.popleft()        if cur:            if len(res) < level+1:                res.append([])            res[level].append(cur.val)            queue.append((cur.left, level+1))            queue.append((cur.right, level+1))    return res我对条件检查感到困惑if len(res) < level+1:   res.append([])，并认为它可以是 '        if cur:            #if len(res) < level+1:            res.append([])            res[level].append(cur.val)            queue.append((cur.left, level+1))            queue.append((cur.right, level+1))    return res为什么需要条件检查？

Answer 1

条件检查在那里，以便res仅当在queue. 如果没有检查，代码将一个新的空数组追加到res为每个节点遇到queue。

让我们看看当您运行带有条件检查的代码时会发生什么。对于您的示例树，首先从队列中弹出值为 3 的根节点。此时的长度res为0，level也是0。所以，len(res) > level + 1是真实的。因此，将附加一个新的空数组res来存储树级别 0 的值。处理级别 1 的第一个节点（值为 9）时的情况也是如此。但是，处理完之后，当我们开始处理级别 1 的第二个节点（值为 20）时，该res数组有 2 个元素（每个级别一个）并且级别的值为 1。len(res) > level + 1为 false 并且没有插入任何内容res。

如果没有那个检查，在迭代结束时 res 数组将是这样的：

[

  [3],

  [9, 20],

  [15, 7],

  [],

  []

]

请注意，因为您的树中有 5 个节点，所以总共附加了 5 个数组，res但只有前 3 个被占用，因为您的树有 3 个级别。