剑指offer 39. 是否为平衡二叉树

 1 class Solution {
 2 public:
 3     bool flag = true;    // 记录是否为平衡二叉树，不是则为false
 4     bool IsBalanced_Solution(TreeNode* pRoot) {
 5         preOrder(pRoot);
 6         return flag;
 7     }
 8     // 前序递归遍历
 9     int preOrder(TreeNode* pRoot){
10         if(pRoot && flag == true){
11             int leftH = preOrder(pRoot->left);
12             int rightH = preOrder(pRoot->right);
13             if(abs(leftH - rightH) > 1)
14                 flag = false;
15             return ((leftH >= rightH) ? (leftH + 1) : (rightH + 1));
16         }
17         return 0;
18     }
19     
20 };

 1 public class Solution {
 2     public boolean IsBalanced_Solution(TreeNode root) {
 3         if(preOrder(root) == -1)
 4             return false;
 5         return true;
 6     }
 7     
 8     // 如果是返回-1， 则表示不是平衡二叉树
 9     public int preOrder(TreeNode root){
10         if(root == null)
11             return 0;
12         int leftH = preOrder(root.left);
13         if(leftH == -1)
14             return -1;        //如果发现子树不平衡之后就没有必要进行下面的高度的求解了
15         int rightH = preOrder(root.right);
16         if(-1 == rightH)       // 如果发现子树不平衡之后就没有必要进行下面的高度的求解了
17             return -1;
18        if((leftH - rightH) > 1 || (leftH - rightH < -1))
19            return -1;
20         return ((leftH >= rightH) ? leftH : rightH) + 1;
21     }
22 }