题目
给定一个二叉树,找出其最小深度。二叉树的最小深度为根节点到最近叶子节点的距离。
http://www.lintcode.com/zh-cn/problem/minimum-depth-of-binary-tree/
分析
由于最小深度计算的是根节点到叶子结点的距离,首先要做的,就是确定叶子结点。根据定义,当给定二叉树节点左右子树都为空时,该节点即为叶子结点。对于根节点root来说,要计算起最小深度,就可能有4种情况:
- root为空,最小深度即为0
- root左子树为空,其最小深度就是右子树的最小深度+1
- root右子树为空,其最小深度就是左子树的最小深度+1
- 左右子树均不为空,其最小深度即为两个子树最小深度取更小的那个值+1
左右子树的最小深度计算,只要递归这个算法即可。
代码实现
public class Solution {
/*
* @param root: The root of binary tree
* @return: An integer
*/
public int minDepth(TreeNode node) {
// write your code here
if(node == null) return 0;
if(node.left == null && node.right == null) return 1;
if( node.left != null && node.right == null){
return minDepth(node.left) + 1;
}
if( node.right != null && node.left == null){
return minDepth(node.right) + 1;
}
int hl = minDepth(node.left);
int hr = minDepth(node.right);
return (hl <= hr ? hl : hr) + 1;
}
}