[剑指Offer] 39.平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

 1 class Solution {
 2 public:
 3     int Get_Height(TreeNode* root) {
 4         if(root == NULL){
 5             return 0;
 6         }
 7         int LeftHeight = Get_Height(root->left);
 8         int RightHeight = Get_Height(root->right);
 9         return max(LeftHeight, RightHeight) + 1;
10     }
11     bool IsBalanced_Solution(TreeNode* pRoot) {
12         if(pRoot == NULL){
13             return true;
14         }
15         if(!IsBalanced_Solution(pRoot->left)){
16             return false;
17         }
18         int LeftHeight = Get_Height(pRoot->left);
19         if(!IsBalanced_Solution(pRoot->right)){
20             return false;
21         }
22         int RightHeight = Get_Height(pRoot->right);
23         if(LeftHeight - RightHeight > 1 || LeftHeight - RightHeight < -1){
24             return false;
25         }
26         return true;
27     }
28 };