时间戳

首页 > 解决方案 > 二叉树的最大深度——我们是否需要一个“持有者”来跟踪当前的最大深度？

python - 二叉树的最大深度——我们是否需要一个“持有者”来跟踪当前的最大深度？

问题描述

我编写代码来解决以下 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 存储在某个地方，并且只保留最大的。我在这一点上是对的吗？

标签： pythontree

解决方案

我的问题是depth = max(current_depth,depth)。我是否正确理解 的唯一目的'depth'是在我们遍历树时充当持有者以保持当前的最大深度？

对，那是正确的。当你用这个等效的代码替换这一行时，也许它有助于澄清这一点：

if current_depth > depth:
    depth = current_depth

我们需要存储current_depth某个地方，只保留最大的。我在这一点上是对的吗？

对，那是正确的。在算法执行期间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 值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)——它不应该在主调用中提供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返回给定的子树的深度，因此没有任何较大树的上下文。在这种情况下，不再需要传递current_depth参数。在进行递归调用后添加 1 ，以说明父节点：

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

推荐阅读