为什么我的二叉树最大深度解决方案返回的结果比预期的少 1？

Question

我正在解决以下 Leetcode 问题： https://leetcode.com/problems/maximum-depth-of-binary-tree/solution/

是到return二叉树的最大深度

这是我的解决方案：

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

        stack = [(root, 1)]
        
        curr_depth = 1
        while stack:
            node, depth = stack.pop()
            depth = max(curr_depth,depth)
            if node.right:
                stack.append((node.right, curr_depth + 1))
            if node.left:
                stack.append((node.left, curr_depth + 1))
        
        return depth

由于某种原因，输出总是比预期的少一个。并查看公认的解决方案，它们看起来与我的非常相似，但我似乎无法找到我的解决方案出错的地方。

Answer 1

这有帮助吗？

from typing import Optional

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self._visit(root, 0)
    
    def _visit(self, node: Optional[TreeNode], depth: int) -> int:
        if not node:
            return depth
        return max(self._visit(node.left, depth + 1), self._visit(node.right, depth + 1))

Answer 2

所以你的违规变量是深度和 curr_depth。基本上当 depth = max(curr_depth,depth) 出现时，你想将其分配给 curr_depth。然后在添加到堆栈时，你想要传递 depth+1 而不是 curr_depth+1，最后你想要 return curr_depth 而不是 depth。 curr_depth 表示当前最大深度，而 depth 是一个临时变量，表示所考虑节点的深度。最好保持一致。

我不会浪费你的时间来复制和粘贴正确的有效算法，正如你所说的，你的问题是关于你的算法失败的原因，因为你已经看到了许多有效的实现。

为什么我的二叉树最大深度解决方案返回的结果比预期的少 1？

Why is my maximum depth solution for binary tree returning one less than it is supposed to?

python

binary-tree