题目

给定一个二叉树，找出其最小深度。二叉树的最小深度为根节点到最近叶子节点的距离。
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;
        
    }
}