为什么我的二叉树最大深度解返回的值比它应该返回的值小？

Question

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

返回二叉树的最大深度。

这是我的解决方案：

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

所以你的问题变量是深度和电流深度。基本上，当出现depth=max（curr\u depth，depth）时，需要将其指定给curr\u depth。然后，在向堆栈中添加要传递的depth 1notcurr_depth 1，最后要返回curr_depth和notdepthcurr_depth表示当前最大深度，depth是一个临时变量，表示所考虑节点的深度。最好是始终如一。

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

Answer 2

这有用吗？

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))