二叉树的最大深度 - 我们是否需要 'holder' 来跟踪最大当前深度？

Question

我正在写代码来解决下面的 leetcode 问题：https://leetcode.com/problems/maximum-depth-of-binary-tree/

这是通过所有测试的迭代解决方案：

def maxDepth(root):
    stack = []

    if not root:
        return 0

    if root:
        stack.append((1,root))

    depth =0

    while stack:
        current_depth, root = stack.pop()

        depth = max(current_depth,depth)
        if root.left:
            stack.append((current_depth+1,root.left))
        if root.right:
            stack.append((current_depth+1,root.right))

    return depth

我大体上理解发生了什么，但我的问题是depth = max(current_depth,depth)。我是否理解 'depth' 的唯一目的是在我们遍历树时作为持有者来持有当前最大深度？

因为最初阅读代码时，首先让我印象深刻的是为什么不只有 current_depth？但后来我想到我们需要将 current_depth 存储在某个地方并且只保留最大的。我在这一点上是对的吗？

Answer 1

my question is with depth = max(current_depth,depth). Am I right in understanding that the only purpose of 'depth' is to act as a holder to hold the current maximum depth as we traverse the tree?

是的，没错。当您将此行替换为以下等效代码时，可能有助于澄清这一点：

if current_depth > depth:
    depth = current_depth

we need to store the current_depth somewhere and only keep the largest. Am I right on this point?

是的，没错。在算法执行期间，current_depth 随着您在堆栈中上下移动而上下波动。实际上，current_depth 总是比 pop 之后的堆栈大小小一（或等于 pop 之前的堆栈大小）所以如果你真的想要，你可以在没有current_depth 变量，并且仅依赖 len(stack)。在那种情况下，您甚至不必将该信息压入堆栈。算法的结果实际上是堆栈在整个执行过程中达到的最大大小：

def maxDepth(root):
    stack = []

    if not root:
        return 0

    if root:
        stack.append(root)

    depth =0

    while stack:
        depth = max(len(stack), depth)
        root = stack.pop()

        if root.left:
            stack.append(root.left)
        if root.right:
            stack.append(root.right)

    return depth

递归版本

您提供的原始代码实际上是递归函数到迭代函数的几乎字面转换，引入了一个显式堆栈变量，而不是您在递归版本中生成的调用堆栈帧。

查看此代码模仿的递归实现也可能有所帮助：

def maxDepth(root):
    if not root:
        return 0

    depth = 0

    def dfs(current_depth, root):  # <-- these variables live on THE stack
        nonlocal depth
        depth = max(current_depth, depth)
        if root.left:
            dfs(current_depth + 1, root.left)
        if root.right:
            dfs(current_depth + 1, root.right)

    dfs(1, root)
    return depth

并将递归树中三个相似的 if 语句移动到更深一层，因此只有一个 if，我们得到：

def maxDepth(root):
    depth = 0

    def dfs(current_depth, root):
        nonlocal depth

        if root:
            depth = max(current_depth, depth)
            dfs(current_depth + 1, root.left)
            dfs(current_depth + 1, root.right)

    dfs(1, root)
    return depth

它本质上是相同的算法，但它可能有助于阐明正在发生的事情。

我们可以把它变成一个更实用的版本，这使得 dfs return 成为 depth 值：这样你就可以避免nonlocal 技巧从该函数内部改变 depth 值：

def maxDepth(root):
    def dfs(current_depth, root):
        return max(current_depth, 
            dfs(current_depth + 1, root.left),
            dfs(current_depth + 1, root.right)
        ) if root else current_depth

    return dfs(0, root)

现在我们甚至可以通过为它提供一个可选参数 (current_depth) 将内部函数与外部函数合并——它不应该在 main[=61 中提供=] 调用 maxDepth:

def maxDepth(root, current_depth=0): return max(current_depth, maxDepth(root.left, current_depth + 1), maxDepth(root.right, current_depth + 1) ) if root else current_depth

最后，最优雅的解决方案是使 maxDepth return 是给定的子树的深度，因此没有大树的任何上下文。在这种情况下，不再需要传递 current_depth 参数。在递归调用后添加1，以说明父节点：

def maxDepth(root): return 1 + max( maxDepth(root.left), maxDepth(root.right) ) if root else 0

二叉树的最大深度 - 我们是否需要 'holder' 来跟踪最大当前深度？

Maximum depth of binary tree- do we need a 'holder' to keep track of the maximum current depth?

python

tree

递归版本