二叉树的镜像

大佬教程收集整理的这篇文章主要介绍了二叉树的镜像，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

描述

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

算法思路

这道题采用的是自顶向下的递归 蓝色子树是已经完成交换的子树，绿色子树是即将进行交换的左子树，绿色子树右边的橙色子树是将要和绿色子树交换的子树

1. 对于当前的 root 交换左右子树

   

2. 交换之后如下

   

3. 对于每个子树的左右子树重复上面第一步的操作，相邻的绿色和橙色子树是将要交换的两个子树

   

代码实现

代码注释详见 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;
    }
};

大佬总结

以上是大佬教程为你收集整理的二叉树的镜像全部内容，希望文章能够帮你解决二叉树的镜像所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。