LeetCode 111. Minimum Depth of Binary Tree

原题

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路一

• 类似于求最大深度时的递归思路
• 不过需要注意的是当某一节点的左子节点(右子节点类似)为空时，不应该参与最小值的比较（否则一定为最小，但是他并不是叶子节点），所以需要返回该节点的右子节点的最小深度

代码实现

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 与求最大深度类似，不过需要注意的是当某一节点左子节点(右子节点类似)有为空的情况时
# 应该不参与最小值的比较，需要返回该节点的右子节点的最小深度
# 这里通过返回right + left + 1简化上述思路
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.helper(root)
        
    def helper(self, node):
        if node == None:
            return 0
        left = self.helper(node.left)
        right = self.helper(node.right)
        return min(right, left) + 1 if (right and left) else right + left + 1

　　

思路二

• 采用正向计数的递归思想

代码实现

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
        
        
# 正向计数递归        
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.dfs(root,0)
        
    def dfs(self,x,level):
        if x==None:return level
        if x.left==None and x.right==None:return level+1
        if x.left!=None and x.right==None:return self.dfs(x.left,level+1)
        if x.left==None and x.right!=None:return self.dfs(x.right,level+1)
        return min(self.dfs(x.left,level+1),self.dfs(x.right,level+1))