C++刷剑指offer(面试题27. 二叉树的镜像)【递归】

糖逗

题目描述：

1. 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
   
2. 
   
3. 例如输入：
   
4. 
   
5.      4
   
6.    /   \
   
7.   2     7
   
8.  / \   / \
   
9. 1   3 6   9
   
10. 镜像输出：
    
11. 
    
12.      4
    
13.    /   \
    
14.   7     2
    
15.  / \   / \
    
16. 9   6 3   1
    
17. 
    
18.  
    
19. 
    
20. 示例 1：
    
21. 
    
22. 输入：root = [4,2,7,1,3,6,9]
    
23. 输出：[4,7,2,9,6,3,1]
    
24.  
    
25. 
    
26. 限制：
    
27. 
    
28. 0 <= 节点个数 <= 1000
    
29. 
    
30. 来源：力扣（LeetCode）
    
31. 链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
    
32. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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

复制代码