描述
操作给定的二叉树，将其变换为源二叉树的镜像。
算法思路
这道题采用的是自顶向下的递归
蓝色子树是已经完成交换的子树，绿色子树是即将进行交换的左子树，绿色子树右边的橙色子树是将要和绿色子树交换的子树
-
对于当前的 root 交换左右子树
-
交换之后如下
-
对于每个子树的左右子树重复上面第一步的操作，相邻的绿色和橙色子树是将要交换的两个子树
代码实现
代码注释详见 c++ 版
递归实现
// c++
class Solution {
public:
// 返回镜像后的树
TreeNode* Mirror(TreeNode* p) {
if (!p) return p;
TreeNode* t = p->right;
p->right = Mirror(p->left); // 返回镜像后的左子树
p->left = Mirror(t); // 返回镜像后的右子树
return p;
}
};
# python3
class Solution:
def Mirror(self , p):
if not p: return p;
p.left, p.right = self.Mirror(p.right), self.Mirror(p.left)
return p
非递归版本代码
实际上就是选定一种顺序访问每个节点，然后交换每个节点的左右子树，下面的代码就是采用先序遍历的方式访问。
// c++
class Solution {
public:
TreeNode* Mirror(TreeNode* p) {
stack<TreeNode*> st;
TreeNode* cur = p;
while (cur || !st.empty()) {
while (cur) {
// 交换 cur 的左子树和右子树
swap(cur->left, cur->right);
st.push(cur);
cur = cur->left;
}
TreeNode* t = st.top();
st.pop();
cur = t->right;
}
return p;
}
};