【树】面试题 04.04. 检查平衡性

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12    // 求深度
13     int depthTree(TreeNode *root)
14     {
15         int depth = 0;
16         if (root)
17         {
18             int leftdepth = depthTree(root->left);
19             int rightdepth = depthTree(root->right);
20 
21             depth = leftdepth > rightdepth ? (leftdepth + 1) : (rightdepth + 1);
22         }
23         return depth;
24     }
25 
26     bool isBalanced(TreeNode* root) 
27     {
28         if (NULL == root)
29         {
30             return true;
31         }
32 
33         int leftdepth = depthTree(root->left);
34         int rightdepth = depthTree(root->right);
35 
36         if (abs(leftdepth - rightdepth) > 1)
37         {
38             return false;
39         }
40         else
41         {
42             return isBalanced(root->left) && isBalanced(root->right);
43         }
44     }
45 };