030-力扣刷题-111--二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7] image.png

另外这道题的关键是搞清楚递归结束条件

叶子节点的定义是左孩子和右孩子都为NULL时叫做叶子节点 当root节点左右孩子都为空时，返回1 当root节点左右孩子有一个为空时，返回不为空的孩子节点的深度 当root节点左右孩子都不为空时，返回左右孩子较小深度的节点值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# 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
        """
        if root is None:  #这个节点对象不存在就返回空
            return 0
        if root.left and root.right:  #这个节点对象左右孩子都存在的时候
            return min(self.minDepth(root.left),self.minDepth(root.right)) + 1 #返回的是下面子树中路径最短的.这个加1加的是当前这个点的一层
        else:
            return max(self.minDepth(root.left),self.minDepth(root.right))+1  #这一个考虑的是这个数的根节点只有一边的树,比如只有右边,那么在这次判断中左孩子不存在返回的是0 ,但是我们不能认为这棵树的深度就是1了,所以返回的应该是大的那个值.这样才能满足条件

第一个if判断的是叶子几点,不会向下延伸,返回值为零 第二个if 是左右节点都有那么就进行递归 第三个的else是下面的这种情况情况 image.png image.png image.png