当我运行一个数组时，为什么我的树节点函数会产生Null？

Question

我正在处理 LeetCode 问题 104。二叉树的最大深度：

给定二叉树的root，返回其最大深度。

二叉树的最大深度是从根节点到最远叶节点的最长路径上的节点数。

我的尝试不起作用：我首先将root添加到队列中（如果root不是 ），然后通过将其子项添加到队列来处理它。

在这样做的同时，我保留一个计数器，每次添加子节点时，我都会将计数器增加1。当左右子节点都存在时，我只会将计数器增加1。

from collections import deque

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

class Solution:
    def max_depth(self,root):
        counter = 1
        queue = deque
        
        if not root: 
            return 0
        else:
            queue.append(root)

        while queue:
            root = queue.popleft()

            if root.left:
                queue.append(root.left)
                counter +=1

            if root.right:
                queue.append(root.right)
                if root.left:
                    continue
                else:
                    counter +=1

        return counter

但是，当我在 LeetCode 上运行上述内容时，对于 [3，9，20，null，null，15，7] 的输入，结果是“无”。

是因为我构建了函数以不将列表作为输入吗？

Answer 1

是因为我构建了函数以不将列表作为输入吗？

不。这可能会令人困惑，但是在LeetCode上，在调用函数之前，输入的原始列表表示被转换为< code>TreeNode的实例。所以你永远不需要处理这个列表结构。它只是LeetCode在不同编程语言中使用的通用输入格式。但是到目标语言数据结构的转换是在调用实现之前完成的。

您的代码在第一次调用< code>queue.append时产生一个错误，原因如下:

queue = deque

这是错误的，因为这会使队列成为类 deque 的同义词。但它应该是它的一个例子，所以：

queue = deque()

通过该修复，该函数不会返回 None。

然而，它的逻辑是不正确的:

我保留了一个计数器，每次添加一个子节点时，我都会将计数器递增1。当左子节点和右子节点都存在时，我只会将计数器增加1。

这实际上意味着计算至少有一个子节点的节点数，即计算树的内部节点数。这是不正确的。例如，下面的树有7个内部节点:

                 ___ 10 __
                /         \
               5           14
             /   \        /   \
            1     8     12     20
           / \   / \   /  \   /  \
          0   2 6   9 11  13 18  22

显然，7不是正确答案。在这种情况下应该是4。

您的基于队列的解决方案将逐级访问节点，但您没有任何关于何时从一个级别传递到下一个级别的信息。

您可以通过使用两个(标准)列表来解决这个问题:第一个列表将包含一个级别的所有节点，第二个列表将收集下一个级别的节点。完成后，你知道你已经处理了一个级别。然后你把第二个列表变成第一个，清空第二个。然后，只要有节点要处理，您就可以重新开始此过程:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        counter = 0
        queue = []
        
        if root: 
            queue.append(root)

        while queue:
            counter +=1
            nextlevel = []
            
            for root in queue:
                if root.left:
                    nextlevel.append(root.left)
                if root.right:
                    nextlevel.append(root.right)
            queue = nextlevel

        return counter

让它更紧凑一点，它可以是：

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        counter = 0
        if root: 
            queue = [root]
            while queue:
                counter +=1
                queue = [root.left for root in queue if root.left
                        ] + [root.right for root in queue if root.right]
        return counter

您也可以进行深度优先遍历，而不是您要进行的宽度优先遍历：

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return 1 + max(self.maxDepth(root.left), 
                       self.maxDepth(root.right)) if root else 0