为什么我的 tree-node 函数在我运行通过它时生成一个数组？

Question

我正在研究 LeetCode 问题 104. Maximum Depth of Binary Tree:

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

我的尝试无效：我首先将 root 添加到队列中（如果 root 不是 None），然后通过添加其 child重新排队。

在做这个的时候，我保留了一个计数器，每添加一个child节点，我就将计数器加1。当左右child都存在时，我只会增加计数器加 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]，结果是 'None' .

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

Answer 1

Is it because I have structured the function to not take a list as an input?

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

您的代码在第一次调用 queue.append 时产生错误，因为这一行：

queue = deque

这是错误的，因为这使得 queue 成为 class deque 的同义词。但它应该是它的一个实例，所以：

queue = deque()

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

但是，它的逻辑是不正确的：

I keep a counter, and each time I add a child node, I increment the counter by 1. When both left and right child exist, I will only increment the counter by 1.

这实际上意味着您计算至少有一个子节点的节点数，即您计算树的 internal 节点数。这是不正确的。例如，下面的树有 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

为什么我的 tree-node 函数在我运行通过它时生成一个数组？

Why is my tree-node function producing Null when I run an array through it?

python

tree

max

为什么我的 tree-node 函数在我 运行 通过它时生成一个数组？

Why is my tree-node function producing Null when I run an array through it?

python

tree

max

为什么我的 tree-node 函数在我运行通过它时生成一个数组？