155. 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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example

Example 1:

Input: {}
Output: 0

Example 2:

Input:  {1,#,2,3}
Output: 3	
Explanation:
	1
	 \ 
	  2
	 /
	3

 

  注意： 如果用普通的递归，那么在helper方法之前要考虑只有一边树的情况（根结点+右子树  root.left == null && root.right != null /跟节点+左子树  root.right == null && root.left != null ）。一定要加&&，否则input为{2}(只有跟节点时)也会进入这个case。如果不考虑一边树的话，会误判左子树的长度为1，那么会minDepth会返回1. 递归法代码： 
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right != null) {
            helper(root.right, 2);
        } else if (root.right == null && root.left != null) {
            helper(root.left, 2);
        } else {
            helper(root, 1);
        }
        return minDepth;
    }
    public void helper(TreeNode root, int curDepth) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            if (curDepth < minDepth) {
                minDepth = curDepth;
            }
            return;
        }
        
        helper(root.left, curDepth + 1);
        helper(root.right, curDepth + 1);
    }
}

 

二分法： 
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getMin(root);
    }

    public int getMin(TreeNode root){
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        return Math.min(getMin(root.left), getMin(root.right)) + 1;
    }
}

 

 
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄