二元树的最小深度

Question

我正在尝试编写代码以找到二进制树的最小深度。

# 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

但是，此解决方案在某些测试用例上不起作用，例如高度不平衡的二进制树，它将其转变为链接列表（ex [2，none，3，3，none，4，4，无，5，无，6]

不计数

     2
    / \
       3
      / \
         4
        / \
           5
          / \
             6

最小深度为5（因为没有孩子 'M亏本，为什么该解决方案不能充分解决此用例？

Answer 1

我认为这是因为 min 函数。从2开始，您的代码检查左侧为0，然后检查右检查并递归检查并返回4。代码> 1 。

Answer 2

您的代码在 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

Answer 3

@Avinash，感谢您的边缘案例。
问题@kellybundy

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