c++刷剑指offer（面试题55 - II. 平衡二叉树）【递归】

糖逗

题目描述：

1. 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
   
2. 
   
3.  
   
4. 
   
5. 示例 1:
   
6. 
   
7. 给定二叉树 [3,9,20,null,null,15,7]
   
8. 
   
9.     3
   
10.    / \
    
11.   9  20
    
12.     /  \
    
13.    15   7
    
14. 返回 true 。
    
15. 
    
16. 示例 2:
    
17. 
    
18. 给定二叉树 [1,2,2,3,3,null,null,4,4]
    
19. 
    
20.        1
    
21.       / \
    
22.      2   2
    
23.     / \
    
24.    3   3
    
25.   / \
    
26. 4   4
    
27. 返回 false 。
    
28. 
    
29.  
    
30. 
    
31. 限制：
    
32. 
    
33. 1 <= 树的结点个数 <= 10000
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. 
   
6. using namespace std;
   
7. 
   
8. struct TreeNode{
   
9.         int val;
   
10.         TreeNode* left;
    
11.         TreeNode* right;
    
12.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
13.         }
    
14. };
    
15. 
    
16. TreeNode* CreateTree(vector<int> input){
    
17.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
18.         for(int i = 0; i < input.size(); i++){
    
19.                 res[i].val = input[i];
    
20.                 res[i].left = NULL;
    
21.                 res[i].right = NULL;
    
22.         }
    
23.         for(int i= 0; i < input.size(); i++){
    
24.                 if(2*i+1 < input.size()){
    
25.                         res[i].left = &res[2*i+1];
    
26.                 }
    
27.                 if(2*i+2 < input.size()){
    
28.                         res[i].right = &res[2*i+2];
    
29.                 }
    
30.                
    
31.         }
    
32.         return res;
    
33.        
    
34. }
    
35. 
    
36. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
37.     if(root == NULL) return;
    
38.     int insert = left + (right - left) / 2;
    
39.     res[depth][insert] = root->val;
    
40.            
    
41.     middle(root->left, res, left, insert - 1, depth + 1);
    
42.     middle(root->right, res, insert + 1, right, depth + 1);
    
43.     }
    
44. 
    
45. int treeDepth(TreeNode* root){
    
46.     if(root == NULL || root -> val == 0) return 0;
    
47.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
48. }
    
49.       
    
50. void printTree(TreeNode* root) {
    
51.     int depth = treeDepth(root);
    
52.     int width = pow(2, depth) - 1;
    
53.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
54.     middle(root, res, 0, width - 1, 0);
    
55.     for(int i = 0; i < res.size(); i++){
    
56.                 for(int j = 0; j < res[i].size();j++){
    
57.                         if(res[i][j] == 0){
    
58.                                 cout  << " ";
    
59.                         }
    
60.                         else{
    
61.                                 cout << res[i][j];
    
62.                         }
    
63.                        
    
64.                 }
    
65.                 cout << endl;
    
66.         }
    
67.         cout << "------------------" << endl;
    
68.     }
    
69. 
    
70. 
    
71. 
    
72. 
    
73. 
    
74. bool solution(TreeNode* root){
    
75.         if(root == NULL) return true;
    
76.         if (abs(treeDepth(root -> right) - treeDepth(root -> left)) > 1) return false;
    
77. 
    
78.         return solution(root -> right) && solution(root -> left);
    
79. }
    
80. 
    
81. int main(void){
    
82.         vector<int> input;
    
83.         cout << "send numbers for the tree" << endl;
    
84.         int number;
    
85.         while(cin >> number){
    
86.                 input.push_back(number);
    
87.         }
    
88.          
    
89.         TreeNode* root = CreateTree(input);
    
90.         printTree(root);
    
91.         bool res  = solution(root);
    
92.         cout << res << endl;
    
93.        
    
94.         return 0;
    
95. }
    

复制代码

注意事项：
1.这里的平衡树是指任意两个节点之间的深度都不能超过1。
2.这里的程序输入0代表NULL值。
3int类型不能被赋予NULL。

糖逗

新增代码：

1. bool solution(TreeNode* root){
   
2.         if(root == NULL) return true;
   
3.         if (abs(treeDepth(root -> right) - treeDepth(root -> left)) > 1) return false;
   
4. 
   
5.         return solution(root -> right) && solution(root -> left);
   
6. }

复制代码

其他代码：
改动少，参考：https://fishc.com.cn/thread-163378-1-1.html

糖逗