<>核心考点:二叉树操作

操作给定的二叉树,将其变换为源二叉树的镜像。

解析:
要将一棵二叉树变化为自身的镜像,只需交换该二叉树每一个结点的左右子树即可。

例如,上述二叉树我们交换根结点的左右子树后源二叉树会发生如下变化。

再继续交换下一层结点的左右子树后,便可得到源二叉树镜像后的二叉树。

但实际上我们还会交换叶子结点的左右子树,只不过叶子结点的左右子树都为空树交换后二叉树无变化。

二叉树都是递归定义的,所以递归操作是比较常见的做法。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ class Solution {
public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr) //空树无需镜像
return nullptr; TreeNode* left = Mirror(pRoot->left); //将该结点的左子树镜像 TreeNode*
right= Mirror(pRoot->right); //将该结点的将右子树镜像 //交换该结点的左右子树 pRoot->left = right;
pRoot->right = left; return pRoot; //返回该结点 } };
但该题目我们只需要将二叉树所有结点的左右子树进行交换即可,所以只要是能遍历二叉树的方法我们都可以使用,下面给出了使用队列和栈解决的方法。

使用队列遍历二叉树进行各结点左右子树的交换。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ class Solution {
public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr) //空树无需镜像
return nullptr; queue<TreeNode*> q; q.push(pRoot); //先将根结点入队列 while (!q.empty())
{ //取队头结点 TreeNode* pNode = q.front(); q.pop(); //交换该结点的左右子树 TreeNode* temp =
pNode->left; pNode->left = pNode->right; pNode->right = temp;
//若该结点的左结点不为空,则将其左结点入队列 if (pNode->left) q.push(pNode->left);
//若该结点的右结点不为空,则将其右结点入队列 if (pNode->right) q.push(pNode->right); } return pRoot;
//返回根结点 } };
使用栈遍历二叉树进行各结点左右子树的交换。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ }; class
Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr)
//空树无需镜像 return nullptr; stack<TreeNode*> st; st.push(pRoot); //先将根结点入栈 while (!
st.empty()) { //取栈顶结点 TreeNode* pNode = st.top(); st.pop(); //交换该结点的左右子树
TreeNode* temp = pNode->left; pNode->left = pNode->right; pNode->right = temp;
//若该结点的左结点不为空,则将其左结点入栈 if (pNode->left) st.push(pNode->left);
//若该结点的右结点不为空,则将其右结点入栈 if (pNode->right) st.push(pNode->right); } return pRoot;
//返回根结点 } };

技术
©2019-2020 Toolsou All rights reserved,
大一上c语言学生管理系统(下)年底了,不要跳槽。字节跳动测试工程师凉经分享教你用Python画一棵圣诞树用C实现圣诞树python 使用turtle 画樱花(python3验证ok)win10系统的计算机C盘在哪,c盘users在哪(win10c盘找不到users)计算机发展史上最著名的两位鼻祖HDFS主要组件(数据块、NameNode、DataNode、secondaryNameNode)python 指定时间运行代码