描述

这是一篇面对初级coder的题解。
知识点：树 递归 DFS
难度：一星

题解

比如：    源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

考察树的基础知识与递归的思路，深度优先搜索。

方法一：递归求解

一个清晰的版本

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot) //判断边界条件，是否为空树 空树递归结束
        {
            /*交换*/
            TreeNode* temp;//定义一个缓冲指针
            temp=pRoot->left;//缓冲左树
            pRoot->left=pRoot->right;//左树等于右树
            pRoot->right=temp;//右树等于左树（缓冲）
            /*递归*/
            pRoot->left=Mirror(pRoot->left);//递归左树
            pRoot->right=Mirror(pRoot->right);//递归右树
        }
        return pRoot;
    }
};

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot) //判断边界条件，是否为空树 空树递归结束
        {
            TreeNode* temp;//定义一个缓冲指针
            temp=Mirror(pRoot->left);//缓冲并镜像左树
            pRoot->left=Mirror(pRoot->right);//左树等于右树
            pRoot->right=temp;//右树等于左树（缓冲）
        }
        return pRoot;
    }
};

用栈实现递归

#include <stack>
class Solution {
public:
    TreeNode* Mirror(TreeNode* root) {
        if(!root) 
            return root; //判断边界条件
        stack<TreeNode*> stack;//定义递归栈
        TreeNode* temp;//定义一个缓冲指针
        stack.push(root);//压入头节点
        while (!stack.empty())
        {
            TreeNode* node = stack.top();
            //头结点出栈
            stack.pop();
            //将左右节点入栈
            if (node->left) 
                stack.push(node->left);
            if (node->right) 
                stack.push(node->right);
            //交换左右节点
            temp = node->left;
            node->left = node->right;
            node->right = temp;
        }
        return root;
    }
};

复杂度分析：

时间复杂度 O(N) ： 其中 NN 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用O(N) 时间。
空间复杂度 O(N)： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间。

总结

递归的解法在树的解题中有广泛应用：

如下动图展示了深度优先搜索的递归算法：

if(!root) 
    return true/false;
if(!root->left) 
    return true/false/递归函数;
if(!root->right) 
    return true/false/递归函数;

if(!p && !q)
    return true/false;
if(!p || !q)
    return true/false;