题解 | #二叉树的镜像#

题目描述

引用内容
操作给定的二叉树，将其变换为源二叉树的镜像。
比如： 源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5
示例1
输入：
{8,6,10,5,7,9,11}

返回值：
{8,10,6,11,9,7,5}

解法一：递归思想

先交换根节点的左右子树的位置，然后向下递归，把左右子树的根节点作为下次循环的根节点。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null || (pRoot.left == null && pRoot.right == null)){
            return pRoot;
        }
        //先交换根节点的左右子树的位置
        TreeNode treeNode = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = treeNode;

        //若左子节点不为null，则进行递归操作
        if(pRoot.left != null){
            Mirror(pRoot.left);
        }
        //若右子节点不为null，则进行递归操作
        if(pRoot.right != null){
            Mirror(pRoot.right);
        }
        return pRoot;
    }
}

复杂度分析：
时间复杂度：O(n)，因为我们遍历整个输入树一次，所以整个运行时间为O(n)，其中n为树中节点的总数。
空间复杂度：递归调用的次数受树的高度限制。在最糟糕的情况下，树是线性的，其高度为O(n)。因此，在最糟糕情况下，由栈上的递归调用造成的空间复杂度为O(n)。

解法二：利用栈结构镜像

除了递归方式，很容易想到先进后出的栈结构，即可使用栈结构遍历所有子节点，并交换每个node的左/右子节点来实现二叉树的镜像。
以下为图简易图解：

代码如下：

  public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null){
            return null;
        }
        //创建辅助栈结构
        Stack<TreeNode> myStack = new Stack<>();
        //将根结点压入栈内
        myStack.push(pRoot);
        while(!myStack.isEmpty()){
                //根节点弹栈
                TreeNode node = myStack.pop();
                //如果根结点不为null，则将其左右子树分别压入栈内
                if(node.left != null){
                    myStack.push(node.left);
                }
                 if(node.right != null){
                    myStack.push(node.right);
                }
               //然后交换左右子树
                TreeNode tmp = node.left;
                node.left = node.right;
                node.right = tmp;

            }

        return pRoot;
    }

复杂度分析：
时间复杂度：O(n)，因为我们遍历整个输入树一次，所以整个运行时间为O(n)，其中n为树中节点的总数。
空间复杂度：最差情况下，栈最多同时存储(n+1)/2 个节点,故空间复杂度为O(n)。