C++刷leetcode（114. 二叉树展开为链表）【递归】

糖逗

题目描述：

1. 给定一个二叉树，原地将它展开为链表。
   
2. 
   
3. 例如，给定二叉树
   
4. 
   
5.     1
   
6.    / \
   
7.   2   5
   
8. / \   \
   
9. 3   4   6
   
10. 将其展开为：
    
11. 
    
12. 1
    
13. \
    
14.   2
    
15.    \
    
16.     3
    
17.      \
    
18.       4
    
19.        \
    
20.         5
    
21.          \
    
22.           6
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

核心代码：

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

复制代码

注意事项：
1.参考链接:https://leetcode-cn.com/problems ... dan-by-xiao-zhu-bu/

糖逗

新增代码：

1. void flatten(TreeNode* root){
   
2.         if(root == NULL) return;
   
3.         if(root -> left != NULL){
   
4.                 TreeNode* temp = root -> left;
   
5.                 while(temp -> right != NULL){
   
6.                         temp = temp -> right;
   
7.                 }
   
8.                 temp -> right = root -> right;
   
9.                 root -> right = root -> left;
   
10.                 root -> left = NULL;
    
11.         }
    
12.         flatten(root -> right);
    
13. }
    
14. 
    
15. void print_right_tree(TreeNode* root){
    
16.         int i = 0;
    
17.         while(root -> right != NULL){
    
18.                 if(root -> val != 0){
    
19.                         cout << root -> val << endl;
    
20.                 }
    
21.                 root = root -> right;
    
22.         }
    
23.         cout << root -> val << endl;
    
24.         return;
    
25. }

复制代码