平衡二叉树

http://www.lintcode.com/zh-cn/problem/balanced-binary-tree/

注意点： 1 在比较子树之间是否是平衡二叉树时，需要用的树的最大深度，最大深度差<1就是平衡。

　　　　　2 3 即，左右子树都平衡且最大深度差<1，则是平衡二叉树。

　　　4　　　 5　　 6

　　　　答案中用-1作为标记，表示树是非平衡二叉树，减少了代码嵌套调用，可以学习。

 1 public boolean isBalanced(TreeNode root) {
 2     if(root == null) return true;
 3     if(isBalanced(root.left) && isBalanced(root.right) && Math.abs(getDep(root.left) - getDep(root.right)) <= 1) return true;
 4     return false;
 5 }
 6 private int getDep(TreeNode root){
 7     if(root == null) return 0;
 8     int left = getDep(root.left);
 9     int right = getDep(root.right);
10     return Math.max(left,right) + 1;
11 }
12 //--------------------答案
13  public boolean isBalanced(TreeNode root) {
14         // write your code here
15        return maxDepth(root) != -1;
16     }   
17     public int maxDepth(TreeNode root) {
18         if(root == null) {
19             return 0;
20         }
21         int left = maxDepth(root.left);
22         int right = maxDepth(root.right);
23         if(left == -1 || right == -1 || Math.abs(right - left) > 1) {
24             return -1;
25         }
26         return Math.max(left,right) + 1;
27     }

View Code

当-1做标记不足以完全表示结果时，定义一个新类来表示。

 1 class ResultType {
 2        boolean isBalance;
 3        int maxDep;
 4        public ResultType(boolean isBalance, int maxDep){
 5            this.isBalance = isBalance;
 6            this.maxDep = maxDep;
 7        }
 8    }
 9    private ResultType helper(TreeNode root) {
10        if(root == null) return new ResultType(true, 0);
11        ResultType left = helper(root.left);
12        ResultType right = helper(root.right);
13        if(!left.isBalance || !right.isBalance || Math.abs(left.maxDep - right.maxDep) > 1)  return new ResultType(false, -1);
14        return new ResultType(true,Math.max(left.maxDep, right.maxDep) + 1);
15    }
16    public boolean isBalanced(TreeNode root) {
17        return helper(root).isBalance;
18    }

View Code

 1  public boolean isBalanced(TreeNode root) {
 2        if(root == null) return true;
 3        return helper(root, 0) != -1;
 4        
 5    }
 6    private int helper(TreeNode root, int dep) {
 7        if(root == null) return dep;
 8        dep++;
 9        int left = helper(root.left, dep);
10        int right = helper(root.right, dep);
11        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
12            return -1;
13        }
14        return Math.max(left,right) + dep;
15    }
16    //上面代码错误，不能传dep，dep描述的是二叉树的最大深度，而并不是子树的深度。
17     public boolean isBalanced(TreeNode root) {
18        return helper(root) != -1;       
19    }
20    private int helper(TreeNode root) {
21        if(root == null) return 0;
22        int left = helper(root.left);
23        int right = helper(root.right);
24        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
25            return -1;
26        }
27        return Math.max(left,right) + 1;
28    }

5-12