我正在尝试编写代码以找到二叉树的最小深度。https://leetcode.com/problems/minimum-depth-of-binary-tree/
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, node):
if node is None:
return 0
else :
# Compute the depth of each subtree
lDepth = self.minDepth(node.left)
rDepth = self.minDepth(node.right)
return min(lDepth, rDepth) + 1
然而，这个解决方案在一些测试用例上不起作用，比如高度不平衡的二叉树，它会变成一个链表(例如[2, None, 3, None, 4, None, 5, None, 6]
)。最小深度为5(因为None子节点不计算)。然而，我的解决方案返回1，所以它必须将2的左子节点视为最小深度叶节点。
2
/
3
/
4
/
5
/
6
我很困惑，为什么这个解决方案不能充分解决这个用例?
我认为这是因为min功能。从2开始，你的代码检查左边是0，然后检查右边是递归检查并返回4。但是，您调用min(0, 4)+1，它会给您输出1。
您的代码在None上停止递归，这不是TreeNode，显然，术语"深度";对于这样的对象是未定义的。尝试在没有子节点的所谓"叶子"节点上停止递归。看看我对这个问题的解决方案:
def is_leaf(node: TreeNode):
return node.left is None and node.right is None
def min_depth(root: TreeNode):
if is_leaf(root):
return 1
not_none_children = (
child if child is not None
for child in (root.left, root.right)]
)
return min(min_depth(child) for child in not_none_children) + 1
@Avinash，谢谢你的边缘情况。@kellyBundy https://leetcode.com/problems/minimum-depth-of-binary-tree/submissions/
class Solution(object):
def minDepth(self, node):
# no node (dead branch)
if node is None:
return 0
lDepth = self.minDepth(node.left)
rDepth = self.minDepth(node.right)
if node.left and node.right:
return min(lDepth, rDepth) + 1
else: #prevents counting first dead branch as minDepth
return max(lDepth, rDepth) + 1