C++刷LeetCode（面试题 04.04. 检查平衡性）【树】【递归】

糖逗

题目描述：

1. 
   
2. 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
   
3. 
   
4. 
   
5. 示例 1:
   
6. 给定二叉树 [3,9,20,null,null,15,7]
   
7.     3
   
8.    / \
   
9.   9  20
   
10.     /  \
    
11.    15   7
    
12. 返回 true 。
    
13. 示例 2:
    
14. 给定二叉树 [1,2,2,3,3,null,null,4,4]
    
15.       1
    
16.      / \
    
17.     2   2
    
18.    / \
    
19.   3   3
    
20. / \
    
21. 4   4
    
22. 返回 false 。

复制代码

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. private:
    
12.     bool res = true;
    
13. public:
    
14.     int depth(TreeNode* curr){//树深度计算
    
15.         if(curr == NULL)return 0;
    
16.         int left = depth(curr -> left);
    
17.         int right = depth(curr -> right);
    
18.         if(abs(left - right) > 1){
    
19.             res = false;
    
20.         }
    
21.         return max(left, right) + 1;
    
22.     }
    
23.     bool isBalanced(TreeNode* root) {
    
24.         //递归
    
25.         depth(root);
    
26.         return res;
    
27.     }
    
28. };

复制代码