题解 | #二叉树的镜像#

描述

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

算法思路

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

1. 对于当前的 root 交换左右子树
   
2. 交换之后如下
   
3. 对于每个子树的左右子树重复上面第一步的操作，相邻的绿色和橙色子树是将要交换的两个子树
   
4. 交换相邻的绿色和橙色子树结果如下
   

   代码实现

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

   两种方法实际上就是把所有节点都访问了一遍，所以时间复杂度都是 O(n)，n为原树的节点数。