[leetcode] Minimum Depth of Binary Tree | 二叉树的最小深度
Posted August 1, 2013
on:- In: leetcode
- 3 Comments
尼玛这破题居然跑了好几遍才对!
一开始错的方法:
public int minDepth(TreeNode root) { if (root == null) return 0; int left = minDepth(root.left); int right = minDepth(root.right); return Math.min(left, right) + 1; }
比如a#b这种左子树为空的树,我直接认为左子树的depth为0了,那当然左子树的depth小,然后parent直接取了0+1。问题在于,某个子树是null的时候,它不是叶子节点啊!这个时候就算没形成一个叶子到root的path,则认为depth为正无穷。改进:
public int minDepth(TreeNode root) { if (root == null) return Intger.MAX_VALUE; if (root.left == null && root.right == null) return 1; //说明是个leaf了! int left = minDepth(root.left); int right = minDepth(root.right); return Math.min(left, right) + 1; }
忍不住回忆为啥做maxdepth的时候就没遇见问题呢?(如下)因为求的是max,所以那种某个子树为0的情况就被Math.max给解决了。总之这种题最好做完了试一试,一试就能立刻看出毛病了,自己干想还真想不到。
public int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }
April 28, 2014 at 5:04 pm
你这如果给个空树给你,不就在
if (root == null)
return Intger.MAX_VALUE;
返了个最大值出来么?还是我看错了?
April 28, 2014 at 5:08 pm
第一句话就是“一开始错的方法“
January 6, 2015 at 7:52 pm
这种做法的话给个空树,层数久违MAX_VALUE了,不过可能没有这种测试数据吧