使用 BFS 的二叉树的最大深度 - 为什么深度加倍？

Question

我正在编写迭代解决方案来查找二叉树的最大深度 - 使用 Breadth First Search (BFS):

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

from collections import deque
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0

        queue = deque()
        queue.append(root)
        depth = 1
        level_length = len(queue)

        while queue: 
            for i in range(level_length): 
                node = queue.popleft() 

                if node.left: 
                    queue.append(node.left)

                if node.right: 
                    queue.append(node.right)
                    
            depth +=1 
            
        return depth

对于输入 root = [3,9,20,null,null,15,7]，我得到 output=6 而不是 3，这显然是正确答案。

我在纸上检查了我的代码好几次，但似乎看不出它的不足之处 - 有什么想法吗？

Answer 1

level_length = len(queue) 仅在遍历开始前计算一次，因此它始终为 1。这意味着您的内部 for 循环永远不会运行超过一次并且实际上不存在，在每个节点上导致 depth += 1 到运行。

将长度计算移到 while 中，以便 for 在递增 depth 之前循环运行每个级别的正确次数。

Leetcode 想要 depth = 0 而不是 depth = 1，但你可能会在修复主要错误后解决这个问题。

使用 BFS 的二叉树的最大深度 - 为什么深度加倍？

maximum depth of a binary tree using BFS- why is the depth doubled what it is supposed to be?

python

algorithm

binary-tree

breadth-first-search