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

糖逗

题目描述：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

 

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
 

限制：

0 <= 节点个数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <malloc.h>
#include<iostream>
#include<math.h>

using namespace std;


struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x):val(x), left(NULL),right(NULL){
        }
};

TreeNode* Create(vector<int>& input){
        TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size() ;i++){
                tree[i].val = input[i];
                tree[i].left = NULL;
                tree[i].right = NULL;
                
        }
        for(int i = 0; i <= input.size()/2-1; i++){
                if(2*i+1 <= input.size()){
                        tree[i].left = &tree[2*i+1]; 
                }
                if(2*i+2<=input.size()){
                        tree[i].right = &tree[2*i+2];
                }
        }
        return tree;
}

TreeNode* solution(TreeNode* root){
        if(root == NULL) return root;
        TreeNode* left_ = solution(root -> left);
        TreeNode* right_ = solution(root -> right);
        root -> right = left_;
        root -> left = right_;
        return root;
        
}


int depth(TreeNode* root){
    if(root == NULL) return 0;
    return max(depth(root->left) + 1, depth(root->right) + 1);
} 

void middle(TreeNode* root, int left, int right, int depth, vector<vector<int> >& res){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
            
    middle(root->left, left, insert - 1, depth + 1, res);
    middle(root->right, insert + 1, right, depth + 1, res);
}



vector<vector<int> > print(TreeNode* root) {
    int depth_ = depth(root);
    int width = pow(2, depth_) - 1;
    vector<vector<int> > res(depth_, vector<int>(width, 0));
    middle(root, 0, width - 1, 0, res);
    return res;
}


void print_vector(vector<vector<int> > input){
        for(int i = 0; i < input.size(); i++){
                for(int j = 0; j < input[i].size(); j++){
                        if(input[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << input[i][j]; 
                        }
                        
                }
                cout << endl;
        }
        cout << "-----------" << endl; 
}

int main(void){
        cout << "please send numbers for the tree:" << endl;
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        TreeNode* root = Create(input);
        vector<vector<int> >temp = print(root);
        print_vector(temp);
        
        TreeNode* new_root = solution(root);
        vector<vector<int> >res = print(new_root);
        print_vector(res);
         
        return 0;
}