描述

这是一篇适合初级学者的题解。这里提供2种方法。
知识点：树，递归
难度：一星

题解

题目抽象：给定一颗二叉树，将二叉树的左右孩子进行翻转，左右孩子的子树做相同的操作。

方法一：递归版本

根据题意，如果我们知道一个根节点的左孩子指针和右孩子指针，那么再改变根节点的指向即可解决问题。
也就是，需要先知道左右孩子指针，再处理根节点。显然对应遍历方式中的后序遍历。
后序遍历的模板：

void postOrder(TreeNode *root) {
    if (!root) return;
    postOrder(root->left); // left child
    postOrder(root->right); // right child
    // process root
}   

这里展示一个例子：

代码

class Solution {
public:
    TreeNode* dfs(TreeNode *r) {
        if (!r) return nullptr;
        TreeNode *lval = dfs(r->left);
        TreeNode *rval = dfs(r->right);
        r->left = rval, r->right = lval;
        return r;
    }
    void Mirror(TreeNode *pRoot) {
        if (!pRoot) return;
        dfs(pRoot);
    }
};

时间复杂度：O(n),n为树节点的个数。每个节点只用遍历一次，所以为O(n)
空间复杂度：O(n), 每个节点都会在递归栈中存一次

方法二：非递归版本

方法一种的递归版本中遍历树的方法用的是后序遍历。所以非递归版本，只需要模拟一次树遍历。
这里模拟树的层次遍历。
层次遍历的模板为：

void bfs(TreeNode *root) {
    queue<TreeNode*> pq;
    pq.push(root);
    while (!pq.empty()) {
        int sz = pq.size();
        while (sz--) {
            TreeNode *node = pq.front(); pq.pop();
            // process node， ours tasks
            // push value to queue
            if (node->left) pq.push(node->left);
            if (node->right) pq.push(node->right);

        } // end inner while
    } // end outer while
}

所以我们的代码为；

class Solution {
public:
    void Mirror(TreeNode *pRoot) {

        queue<TreeNode*> pq;
        pq.push(pRoot);
        while (!pq.empty()) {
            int sz = pq.size();
            while (sz--) {
                TreeNode *node = pq.front(); 
                pq.pop();

                if (node->left) pq.push(node->left);
                if (node->right) pq.push(node->right);
                // our tasks
                TreeNode *cur = node->left; // 需要保存一下
                node->left = node->right;
                node->right = cur;


            } // end inner while

        } // end outer while
    }
};

时间复杂度：O(n),n为树节点的个数。每个节点只用遍历一次，所以为O(n)
空间复杂度：O(n)