http://www.lintcode.com/zh-cn/problem/maximum-depth-of-binary-tree/
注意点:下面代码不行的,maxDepth传入函数是值传递,不是地址传递,所以它的值是不会变的,最后的值还是0;
要解决这个问题,可以不把maxDepth作为参数传到函数里; 那就给helper 返回int。
private int maxDepth = 0;
public int maxDepth(TreeNode root) {
if(root == null) return maxDepth;
helper(root, 0, maxDepth);
return maxDepth;
}
private void helper(TreeNode root, int curDep, int maxDepth) {
if(root == null) return;
curDep++;
if(curDep > maxDepth) maxDepth =curDep;
helper(root.left,curDep,maxDepth);
helper(root.right,curDep,maxDepth);
return;
}
//修改如下:
private int maxDepth = 0;
public int maxDepth(TreeNode root) {
if(root == null) return maxDepth;
return helper(root, 0, maxDepth);
}
private int helper(TreeNode root, int curDep, int maxDepth) {
if(root == null) return maxDepth;
curDep++;
if(curDep > maxDepth) maxDepth =curDep;
int left = helper(root.left,curDep,maxDepth);
int right = helper(root.right,curDep,maxDepth);
return Math.max(left, right);
}
1 public int maxDepth(TreeNode root) { 2 int dep = 0; 3 if(root == null) return dep; 4 int left = maxDepth(root.left); 5 int right = maxDepth(root.right); 6 return Math.max(left,right) + 1; 7 } 8 //上一个是分治的思想,下一个是将result作为参数在函数中传递, 9 //类似二叉树遍历里的traverse。(返回空即可 ) 10 private int dep = 0; 11 public int maxDepth(TreeNode root) { 12 helper(root, 0); 13 return dep; 14 } 15 16 private void helper(TreeNode root, int currDep) { 17 if(root == null) return; 18 currDep++; 19 if(currDep > dep) dep = currDep; 20 helper(root.left, currDep); // 1 21 helper(root.right, currDep); // 2 null 此情况下,left的currDep++,且dep = currDep; 22 // 而right的currDep没变,也不会影响到dep。 23 // 如果null换成3,right的currDep++,还是不会影响到dep。 24 }