[Leetcode] 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.

Solution:

第一次提交的错误的代码。

比如a#b这种左子树为空的树，我直接认为左子树的depth为0了，那当然左子树的depth小，然后parent直接取了0+1。问题在于，某个子树是null的时候，它不是叶子节点啊！这个时候就算没形成一个叶子到root的path，则认为depth为正无穷。

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

修改过后正确的代码是：

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int minDepth(TreeNode root) {
12         if(root==null)
13             return 0;
14         if(root.left==null&&root.right==null)
15             return 1;
16         int lDepth=minDepth(root.left);
17         int rDepth=minDepth(root.right);
18         if(root.left==null){
19             lDepth=Integer.MAX_VALUE;
20         }
21         if(root.right==null){
22             rDepth=Integer.MAX_VALUE;
23         }
24         return Math.min(rDepth,lDepth )+1;
25     }
26 }