首页 > 代码库 > 剑指Offer17 二叉树的镜像

剑指Offer17 二叉树的镜像

  1 /*************************************************************************  2     > File Name: 17_MirrorOfBinaryTree.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年08月30日 星期二 17时10分03秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <stdlib.h> 10 #include <malloc.h> 11 #include <bits/stdc++.h> 12  13 using namespace std; 14  15 // 二叉树结构体 16 struct TreeNode 17 { 18     int val; 19     TreeNode* left; 20     TreeNode* right; 21 }; 22  23 TreeNode* createTree() 24 { 25     TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); 26     root->val = 8; 27     root->left = (TreeNode*)malloc(sizeof(TreeNode)); 28     root->left->val = 8; 29     root->right = (TreeNode*)malloc(sizeof(TreeNode)); 30     root->right->val = 7; 31     root->right->left = NULL; 32     root->right->right = NULL; 33     root->left->left = (TreeNode*)malloc(sizeof(TreeNode)); 34     root->left->left->val = 9; 35     root->left->left->left = NULL; 36     root->left->left->right = NULL; 37     root->left->right = (TreeNode*)malloc(sizeof(TreeNode)); 38     root->left->right->val = 2; 39     root->left->right->left = (TreeNode*)malloc(sizeof(TreeNode)); 40     root->left->right->left->val = 4; 41     root->left->right->left->left = NULL; 42     root->left->right->left->right = NULL; 43     root->left->right->right = (TreeNode*)malloc(sizeof(TreeNode)); 44     root->left->right->right->val = 7; 45     root->left->right->right->left = NULL; 46     root->left->right->right->right = NULL; 47      48     return root; 49 } 50  51 void Mirror(TreeNode* root) 52 { 53     if (root == NULL) 54         return; 55     if (root->left==NULL && root->right==NULL) 56         return; 57      58     TreeNode* temp = root->left; 59     root->left = root->right; 60     root->right = temp; 61      62     if (root->left) 63         Mirror(root->left); 64     if (root->right) 65         Mirror(root->right); 66 } 67  68 // 层序遍历二叉树 69 void PrintTreeByLevel(TreeNode* root) 70 { 71     if (root == NULL) 72         return; 73      74     vector<TreeNode*> vec; 75     vec.push_back(root); 76     int cur = 0; 77     int last = 1; 78      79     while (cur < vec.size()) 80     { 81         last = vec.size(); 82         while (cur < last) 83         { 84             printf("%d ", vec[cur]->val); 85             if (vec[cur]->left != NULL) 86                 vec.push_back(vec[cur]->left); 87             if (vec[cur]->right != NULL) 88                 vec.push_back(vec[cur]->right); 89              90             ++ cur; 91         } 92         printf("\n"); 93     } 94 } 95  96 int main() 97 { 98     TreeNode* tree = createTree(); 99     100     PrintTreeByLevel(tree);101     printf("\n");102     103     Mirror(tree);104     PrintTreeByLevel(tree);105     106     return 0;107 }

 

剑指Offer17 二叉树的镜像