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

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

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

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

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

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

二叉树都是递归定义的,所以递归操作是比较常见的做法。
/* 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语言)总结G1垃圾收集器面试题Android中使用微信H5支付时支付结果刷新问题32-jdbc工具类大学里要参加竞赛吗?都有哪些竞赛可以参加?震惊!!C++居然可以发出声音!C语言之链表入门(超详解)Java实现一个疫情人数管理系统如何用python实现斐波那契数列的前100个MyBatis循环Map(高级用法)