minimum-depth-of-binary-tree

发表于   |   分类于   |  

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

tree1
此时，树的最短高为2
当有一颗子树为空时，最短高为另一颗高度加1
当子树都不为空时，为left和right的最短高加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
       if(root==null)
           return 0;
       int left=run(root.left);
       int right=run(root.right);
       if(left==0) return right+1;
       if(right==0) return left+1;
       return Math.min(left,right)+1;
    }
}