1.翻转一棵二叉树。
//前序遍历
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x)
{
val=x;
left=NULL;
right=NULL;
}
};
TreeNode* invertTree(TreeNode* root)
{
if(root==NULL)
{
return root;
}
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
vector<vector<int>> leveltrversal(TreeNode* root)
{
queue<TreeNode*> que;
if(root!=NULL)
{
que.push(root);
}
vector<vector<int>> res;
while(!que.empty())
{
vector<int> result;
int size=que.size();
while(size--)
{
TreeNode* node=que.front();
que.pop();
result.push_back(node->val);
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
res.push_back(result);
}
return res;
}
int main()
{
TreeNode* root=new TreeNode(1);
root->left=new TreeNode(2);
root->right=new TreeNode(3);
root->left->left=new TreeNode(4);
root->left->right=new TreeNode(5);
root->right->left=new TreeNode(6);
root->right->right=new TreeNode(7);
invertTree(root);
vector<vector<int>> result= leveltrversal(root);
for(const auto& level:result)
{
for(int n:level)
{
cout<<n<<" ";
}
cout<<endl;
}
return 0;
}
思路：对于这道题，首先我们要理解要翻转二叉树，其实是改变指针，而并不是将值改变，左右子树交换位置，同时它们的左右子树也会随之交换。
首先对于前序遍历，如果根不为空，那么就交换其左右子树（swap（）），接着递归其左子树，最后递归其右子树（当然前提是左右子树存在）。（前序--中左右的顺序）
为了知道最后是否成功将二叉树翻转，层序遍历一下检查。
//后序遍历
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x)
{
val=x;
left=NULL;
right=NULL;
}
};
TreeNode* invertTree(TreeNode* root)
{
if(root==NULL)
{
return root;
}
invertTree(root->left);
invertTree(root->right);
swap(root->left,root->right);
return root;
}
vector<vector<int>> leveltrversal(TreeNode* root)
{
queue<TreeNode*> que;
if(root!=NULL)
{
que.push(root);
}
vector<vector<int>> res;
while(!que.empty())
{
vector<int> result;
int size=que.size();
while(size--)
{
TreeNode* node=que.front();
que.pop();
result.push_back(node->val);
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
res.push_back(result);
}
return res;
}
int main()
{
TreeNode* root=new TreeNode(1);
root->left=new TreeNode(2);
root->right=new TreeNode(3);
root->left->left=new TreeNode(4);
root->left->right=new TreeNode(5);
root->right->left=new TreeNode(6);
root->right->right=new TreeNode(7);
invertTree(root);
vector<vector<int>> result= leveltrversal(root);
for(const auto& level:result)
{
for(int n:level)
{
cout<<n<<" ";
}
cout<<endl;
}
return 0;
}
思路：大致与前序遍历差不多，就是遍历顺序不同，（后序--左右中），因此先递归左子树，后递归右子树，最后才交换中节点。
//中序遍历
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x)
{
val=x;
left=NULL;
right=NULL;
}
};
TreeNode* invertTree(TreeNode* root)
{
if(root==NULL)
{
return root;
}
invertTree(root->left);
swap(root->left,root->right);
invertTree(root->left);
return root;
}
vector<vector<int>> leveltrversal(TreeNode* root)
{
queue<TreeNode*> que;
if(root!=NULL)
{
que.push(root);
}
vector<vector<int>> res;
while(!que.empty())
{
vector<int> result;
int size=que.size();
while(size--)
{
TreeNode* node=que.front();
que.pop();
result.push_back(node->val);
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
res.push_back(result);
}
return res;
}
int main()
{
TreeNode* root=new TreeNode(1);
root->left=new TreeNode(2);
root->right=new TreeNode(3);
root->left->left=new TreeNode(4);
root->left->right=new TreeNode(5);
root->right->left=new TreeNode(6);
root->right->right=new TreeNode(7);
invertTree(root);
vector<vector<int>> result= leveltrversal(root);
for(const auto& level:result)
{
for(int n:level)
{
cout<<n<<" ";
}
cout<<endl;
}
return 0;
}
思路：这里因为中序遍历顺序是左右中，先递归左子树，再交换左右子树，注意此时右子树的元素已经换到了左子树位置，因此最后递归的仍是左子树！！！