first

2017-03-22

###Problem:
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.

###Solution
基本思想是递归左子树为空时,返回右子树+1,右子树为空时返回左子树+1,都不为空返回较小者。
深度遍历其实效率很低。

public class Solution {
public int run(TreeNode root) {
    if(root == null) return 0;
    if(root.left == null && root.right == null)
        return 1;
    if(root.left == null)
        return run(root.right) + 1;
    if(root.right == null)
        return run(root.left) + 1;
    return Math.min(run(root.left), run(root.right)) + 1;

  }

}
用层次便利能达到较好的效果。