27. 二叉树的镜像【递归/辅助栈】

1. 问题

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

2. 解法 - 递归

2.1 Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//递归
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 递归出口：遍历到叶子结点时返回空
        if (root == null)
            return null;

        // 利用工具人tmp暂存一下左子树
        TreeNode tmp = root.left;
        // 递归右子树，把返回值作为root的左子树
        root.left = mirrorTree(root.right);
        // 递归左子树，把返回值作为root的右子树
        root.right = mirrorTree(tmp);
        // 返回根节点
        return root;
    }
}

2.2 Kotlin

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun mirrorTree(root: TreeNode?): TreeNode? {
        // 递归出口：遍历到叶子结点时返回空
        if (root == null)
            return null

        // 利用工具人tmp暂存一下左子树
        val tmp = root.left
        // 递归右子树，把返回值作为root的左子树
        root.left = mirrorTree(root.right)
        // 递归左子树，把返回值作为root的右子树
        root.right = mirrorTree(tmp)
        // 返回根节点
        return root
    }
}

2.3 复杂度分析

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

3. 解法 - 辅助栈

可以用辅助栈或者队列。

3.1 Java

//辅助栈
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 特判，根为空直接返回空
        if(root == null) 
            return null;

        // 辅助栈
        Stack<TreeNode> stack = new Stack<>();

        // 初始化，添加根结点
        stack.add(root);

        // 当辅助栈为空时跳出循环
        while(!stack.isEmpty()) {
            // 先把当前结点pop出来
            TreeNode curNode = stack.pop();

            // 如果当前节点的左结点不为空，就把左节点加入到辅助栈中
            if(curNode.left != null) 
                stack.add(curNode.left);
            // 如果当前节点的右结点不为空，就把右节点加入到辅助栈中
            if(curNode.right != null) 
                stack.add(curNode.right);
            
            // 交换当前结点的左右结点
            TreeNode tmp = curNode.left;
            curNode.left = curNode.right;
            curNode.right = tmp;
        }

        // 返回root，此时已经完成镜像
        return root;
    }
}

3.2 Kotlin

// 辅助栈
class Solution {
    fun mirrorTree(root: TreeNode?): TreeNode? {
        // 特判，根为空直接返回空
        if (root == null)
            return null

        // 辅助栈
        val stack = Stack<TreeNode>()

        // 初始化，添加根结点
        stack.add(root)

        // 当辅助栈为空时跳出循环
        while (!stack.isEmpty()) {
            // 先把当前结点pop出来
            val curNode = stack.pop()

            // 如果当前节点的左结点不为空，就把左节点加入到辅助栈中
            if (curNode.left != null)
                stack.add(curNode.left)
            // 如果当前节点的右结点不为空，就把右节点加入到辅助栈中
            if (curNode.right != null)
                stack.add(curNode.right)

            // 交换当前结点的左右结点
            val tmp = curNode.left
            curNode.left = curNode.right
            curNode.right = tmp
        }

        // 返回root，此时已经完成镜像
        return root
    }
}

3.3 复杂度分析

时间复杂度O(N)：其中N为二叉树的结点数量，建立二叉树镜像需要遍历树的所有结点，占用O(N)时间。
空间复杂度O(N)：当处于最差情况下，即该二叉树为满二叉树时，辅助栈最多同时存储N/2个节点，占用O(N)额外空间。

4. 参考

上一页26. 树的子结构【递归】下一页28. 对称的二叉树【递归】

最后更新于3年前