Leetcode 111.二叉树的最小深度

Time: 20190901
Type: Easy

题目描述

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

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

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

示例:

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

3/\920/\157

返回它的最小深度 2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归求解。

代码

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defminDepth(self,root:TreeNode)->int:ifnotroot:return0left=self.minDepth(root.left)right=self.minDepth(root.right)return1+min(left,right)if(leftandright)else(1+left+right)

站在当前结点思考，左右子树均存在时，取最低高度的子树加上1得到当前高度，若左子树或右子树为空，则只能计算非空子树的高度加上1，可以举个例子辅助理解。

END.