当树的一侧为空时，查找二叉树解决方案的最小深度不起作用

Question

我试图理解为什么当树的一侧是 None 时我找到二叉树最小深度的解决方案不起作用。

这里已经有人问过这个问题了 - 但那里的答案仍然没有让我理解。

我的实现代码如下

class Solution:
    def minDepth(self, root: 'TreeNode') -> 'int':
        if root is None:
            return 0

        left = self.minDepth(root.left)
        right = self.minDepth(root.right)

        min_depth = min(left, right)

        return 1 + min_depth

当最后一行修改为以下内容时，就可以了。

    if left == 0 or right == 0:
        return 1 + left + right

    return 1 + min_depth

我的问题是，为什么你需要检查一侧是否是 None，如果最后你把它们全部加起来 - return 1 + left + right?

测试用例是

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# [1, 2]
root = TreeNode(1)
root.left = TreeNode(2)

solution = Solution()
solution.minDepth(root)

我的代码 returns 1 它应该 return 2.

编辑树的深度定义为从树根到叶节点的最短路径中的节点数。

Answer 1

当您位于只有一个 child 的节点时，那么在您的第一个代码版本中，该节点的 min_depth 将为 0（因为其中一个递归调用将 return0).

那确实是错误的，因为节点不是叶子。只有当节点是叶子（没有 children）时才是正确的。

在你的例子中，根就是这样一个节点（有一个child）。这是发生了什么：

minDepth(root)被称为
.....minDepth(root.left) 被称为
.......minDepth(root.left.left) is called and returns 0, because it isNone`
.......minDepth(root.left.right) is called and returns 0, because it isNone`
.......min_depth = min(left, right) 计算结果为 0
....... return 值为 1 minDepth(root.left)
.....minDepth(root.right) 被调用并且 returns 0，因为它是 None
.....min_depth = min(left, right) 计算结果为 0，这是错误的。
...最终的 return 值为 1（错误）。

当你遇到left或right其中一个为0的情况时，你需要得到剩下的child的minDepth并加1 .这就是为什么当你添加这个时它起作用的原因：

if left == 0 or right == 0:
    return 1 + left + right

当树的一侧为空时，查找二叉树解决方案的最小深度不起作用

Find minimum depth of binary tree solution does not work when one side of tree is null

python

binary-tree

python-3.x