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.
A:
public class MinimumDepthOfBinaryTree { public int minDepth(TreeNode root) { if(root==null){ return 0; }else if(root.left==null && root.right==null){ return 1; }else if(root.left==null && root.right !=null){ return 1+minDepth(root.right); }else if(root.left !=null && root.right==null){ return 1+minDepth(root.left); }else{ return 1+ Math.min(minDepth(root.left), minDepth(root.right)); } } }
Mistakes:
1:
注意,这里的depth,不是我们通常所理解的(edge的条数)而是node的数量。
我们设了root==null时, depth =-1. 这样,为了不考虑root.left == null,(或者root.right==null)时的情况。
但是,当root真为空的时候,depth就返回了-1,而不是0了。
2: 注意,题目里,是到nearest left node. 因此,当输入是{1,2}的时候,我们不能考虑
-------------------第二遍-----------------题目理解错误, 要求是nearest leaf node ---------而若一个节点,有左,或者右 child的话,是不能算的。
public class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null){ return 1+ minDepth(root.right); } if(root.right == null){ return 1+ minDepth(root.left); } // NOW both children are not null int left = minDepth(root.left); int right = minDepth(root.right); return 1 + Math.min(left,right); } }
No comments:
Post a Comment