C++刷剑指offer(面试题27. 二叉树的镜像)【递归】
本帖最后由 糖逗 于 2020-5-8 18:10 编辑题目描述：
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root =
输出：
限制：
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.val = input;
tree.left = NULL;
tree.right = NULL;
}
for(int i = 0; i <= input.size()/2-1; i++){
if(2*i+1 <= input.size()){
tree.left = &tree;
}
if(2*i+2<=input.size()){
tree.right = &tree;
}
}
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 = 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.size(); j++){
if(input == 0){
cout<< " ";
}
else{
cout << input;
}
}
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;
}
页:
[1]