C++刷leetcode（99. 恢复二叉搜索树）【递归】

糖逗

题目描述：

1. 
   
2. 二叉搜索树中的两个节点被错误地交换。
   
3. 
   
4. 请在不改变其结构的情况下，恢复这棵树。
   
5. 
   
6. 示例 1:
   
7. 
   
8. 输入: [1,3,null,null,2]
   
9. 
   
10.    1
    
11.   /
    
12. 3
    
13.   \
    
14.    2
    
15. 
    
16. 输出: [3,1,null,null,2]
    
17. 
    
18.    3
    
19.   /
    
20. 1
    
21.   \
    
22.    2
    
23. 示例 2:
    
24. 
    
25. 输入: [3,1,4,null,null,2]
    
26. 
    
27.   3
    
28. / \
    
29. 1   4
    
30.    /
    
31.   2
    
32. 
    
33. 输出: [2,1,4,null,null,3]
    
34. 
    
35.   2
    
36. / \
    
37. 1   4
    
38.    /
    
39.   3
    
40. 进阶:
    
41. 
    
42. 使用 O(n) 空间复杂度的解法很容易实现。
    
43. 你能想出一个只使用常数空间的解决方案吗？

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. #include<algorithm>
   
7. using namespace std;
   
8. 
   
9. struct TreeNode{
   
10.         int val;
    
11.         TreeNode* left;
    
12.         TreeNode* right;
    
13.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
14.         }
    
15. };
    
16. 
    
17. TreeNode* CreateTree(vector<int> input){
    
18.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
19.         for(int i = 0; i < input.size(); i++){
    
20.                 res[i].val = input[i];
    
21.                 res[i].left = NULL;
    
22.                 res[i].right = NULL;
    
23.         }
    
24.         for(int i= 0; i < input.size(); i++){
    
25.                 if(2*i+1 < input.size()){
    
26.                         res[i].left = &res[2*i+1];
    
27.                 }
    
28.                 if(2*i+2 < input.size()){
    
29.                         res[i].right = &res[2*i+2];
    
30.                 }
    
31.                
    
32.         }
    
33.         return res;
    
34.         
    
35. }
    
36. 
    
37. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
38.     if(root == NULL) return;
    
39.     int insert = left + (right - left) / 2;
    
40.     res[depth][insert] = root->val;
    
41.            
    
42.     middle(root->left, res, left, insert - 1, depth + 1);
    
43.     middle(root->right, res, insert + 1, right, depth + 1);
    
44.     }
    
45. 
    
46. int treeDepth(TreeNode* root){
    
47.     if(root == NULL || root -> val == 0) return 0;
    
48.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
49. }
    
50.       
    
51. void PrintTree(TreeNode* root) {
    
52.     int depth = treeDepth(root);
    
53.     int width = pow(2, depth) - 1;
    
54.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
55.     middle(root, res, 0, width - 1, 0);
    
56.     for(int i = 0; i < res.size(); i++){
    
57.                 for(int j = 0; j < res[i].size();j++){
    
58.                         if(res[i][j] == 0){
    
59.                                 cout  << " ";
    
60.                         }
    
61.                         else{
    
62.                                 cout << res[i][j];
    
63.                         }
    
64.                        
    
65.                 }
    
66.                 cout << endl;
    
67.         }
    
68.         cout << "------------------" << endl;
    
69.     }
    
70. 
    
71. 
    
72. 
    
73. void inorder(TreeNode* root, vector<int>& temp){
    
74.         if(root == NULL) return;
    
75.         inorder(root -> left, temp);
    
76.         if(root -> val != 0)temp.push_back(root -> val);
    
77.         inorder(root -> right, temp);
    
78. }
    
79. 
    
80. void rever(TreeNode* root, vector<int>& temp){
    
81.         if(root == NULL) return;
    
82.         rever(root -> left, temp);
    
83.         if(root -> val != 0){
    
84.                 if(root -> val != temp.front()){
    
85.         root -> val = temp.front();
    
86.         temp.erase(temp.begin());
    
87.             }
    
88.             else{
    
89.                 temp.erase(temp.begin());
    
90.             }
    
91.         }
    
92.        
    
93. 
    
94.         rever(root -> right, temp);
    
95. }
    
96. 
    
97. void solution(TreeNode* root) {
    
98.     if(root == NULL) return;
    
99.         vector<int> temp;
    
100.         inorder(root, temp);
     
101.         sort(temp.begin(), temp.end());
     
102.         for(int i =0; i < temp.size(); i++){
     
103.                 cout << temp[i]        << " ";
     
104.         }
     
105.         cout << endl;
     
106.         rever(root, temp);
     
107.        
     
108.         return;
     
109.    
     
110. }
     
111. 
     
112. 
     
113. 
     
114. int main(void){
     
115.         vector<int> input;
     
116.         int number;
     
117.         while(cin >> number){
     
118.                 input.push_back(number);
     
119.                 }
     
120.                 TreeNode* root = CreateTree(input);
     
121.                 PrintTree(root);
     
122.                 solution(root);
     
123.                 PrintTree(root);
     
124.                
     
125.         return 0;
     
126. }
     

复制代码

注意事项：
1.中序遍历的二叉查找树的升序排列。
2.自己定义的树是用0代表缺失值的所以和leetcode上有些许不同（做了节点值是否为0的判断）。

糖逗

新增代码

1. void inorder(TreeNode* root, vector<int>& temp){
   
2.         if(root == NULL) return;
   
3.         inorder(root -> left, temp);
   
4.         if(root -> val != 0)temp.push_back(root -> val);
   
5.         inorder(root -> right, temp);
   
6. }
   
7. 
   
8. void rever(TreeNode* root, vector<int>& temp){
   
9.         if(root == NULL) return;
   
10.         rever(root -> left, temp);
    
11.         if(root -> val != 0){
    
12.                 if(root -> val != temp.front()){
    
13.         root -> val = temp.front();
    
14.         temp.erase(temp.begin());
    
15.             }
    
16.             else{
    
17.                 temp.erase(temp.begin());
    
18.             }
    
19.         }
    
20.       
    
21. 
    
22.         rever(root -> right, temp);
    
23. }
    
24. 
    
25. void solution(TreeNode* root) {
    
26.     if(root == NULL) return;
    
27.         vector<int> temp;
    
28.         inorder(root, temp);
    
29.         sort(temp.begin(), temp.end());
    
30.         for(int i =0; i < temp.size(); i++){
    
31.                 cout << temp[i]        << " ";
    
32.         }
    
33.         cout << endl;
    
34.         rever(root, temp);
    
35.       
    
36.         return;
    
37.    
    
38. }

复制代码