二叉树最小深度

题目

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

Get the latest posts delivered right to your inbox.