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

Question

我试图解决二叉树级别顺序遍历问题 - LeetCode

给定一棵二叉树，返回其节点值的层序遍历。（即从左到右，一层一层）。

例如：给定二叉树[3,9,20,null,null,15,7]，

    3

   / \

  9  20

    /  \

   15   7

返回其层序遍历为：

[

  [3],

  [9,20],

  [15,7]

]

我的方案很直观，BFS遍历收集每一层的值

from collections import deque

class 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 + deque

def 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 数组将是这样的：[&nbsp; [3],&nbsp; [9, 20],&nbsp; [15, 7],&nbsp; [],&nbsp; []]请注意，因为您的树中有 5 个节点，所以总共附加了 5 个数组，res但只有前 3 个被占用，因为您的树有 3 个级别。