110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

代碼如下：

 1 /**
 2  * Definition for a binary tree node.
 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     
12     public boolean isBalanced(TreeNode root) {
13       if(root==null)
14       return true;
15       
16       if(DFS(root)==-1)
17       return false;
18       
19       return true;
20       
21     }
22     
23     public int DFS(TreeNode root){
24         int left=1,right=1;
25         if(root.left!=null)
26         {
27             if(DFS(root.left)==-1)
28             return -1;
29             else
30             left=left+DFS(root.left);
31         }
32         if(root.right!=null)
33         {
34             if(DFS(root.right)==-1)
35             return -1;
36             else
37             right=right+DFS(root.right);
38         }
39         
40         if(left-right<-1||left-right>1)
41         return -1;
42         
43         return Math.max(left,right);
44     }
45    
46 }