剑指offer | 面试题21：二叉树的镜像

千羽

发布于 2021-12-29 13:18:56

1790

发布于 2021-12-29 13:18:56

文章被收录于专栏：程序员千羽

死磕算法系列文章

“Leetcode : https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_21_mirrorTree/Solution.java

剑指 Offer 20. 二叉树的镜像

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

例如输入：

        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

分析

二叉树镜像定义： 对于二叉树中任意节点 root ，设其左 / 右子节点分别为 left, right；则在二叉树的镜像中的对应 root节点，其左 / 右子节点分别为 right, left 。

方法一：递归法

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

递归解析：

终止条件： 当节点 root为空时（即越过叶节点），则返回 null ；
递推工作：
1. 初始化节点tmp,用于暂存root的左子节点; .
2. 开启递归右子节点mirrorTree(root.right)，并将返回值作为root的左子节点。
3. 开启递归左子节点mirrorTree(tmp) ,并将返回值作为root的右子节点。
返回值:返回当前节点root ;

“Q:为何需要暂存root的左子节点? A:在递归右子节点“root.left = mirrorTree(root.right);"执行完毕后，root.left 的值已经发生改变,此时递归左子节点mirrorTree(root.left)则会出问题。

复杂度分析:

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

package com.nateshao.sword_offer.topic_21_mirrorTree;

import java.util.Stack;

/**
 * @date Created by 邵桐杰 on 2021/11/24 22:48
 * @微信公众号 程序员千羽
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: 剑指 Offer 27. 二叉树的镜像
 */
public class Solution {
    /**
     * 递归
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode node = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(node);
        return root;
    }

    /**
     * 解法一：递归，时间复杂度：O(n)，空间复杂度：O(n)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null) return true;
        if (leftNode == null || rightNode == null) return false;

        return leftNode.val == rightNode.val && isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}

方法二：辅助栈(或队列)

利用栈(或队列)遍历树的所有节点node，并交换每个node的左/右子节点。

算法流程：

特例处理： 当root为空时，直接返回null ;
初始化： 栈(或队列)，本文用栈，并加入根节点root 。
循环交换： 当栈 stack为控时跳出;
1. 出栈：记为node ;
2. 添加子节点：将node左和右子节点入栈;
3. 交换：交换node的左1右子节点。
返回值：返回根节点root。

复杂度分析:

时间复杂度0(N) ：其中N为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用O(N)时间。
空间复杂度O(N) ：如下图所示,最差情况下，栈stack最多同时存储N+1/2个节点，占用O(N)额外空间。

package com.nateshao.sword_offer.topic_21_mirrorTree;

import java.util.Stack;

/**
 * @date Created by 邵桐杰 on 2021/11/24 22:48
 * @微信公众号 程序员千羽
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: 剑指 Offer 27. 二叉树的镜像
 */
public class Solution {
    /**
     * 栈
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree1(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<TreeNode>() {{
            add(root);
        }};
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) stack.add(node.left);
            if (node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
    /**
     * 解法二：迭代，时间复杂度：O(n)，空间复杂度：O(n)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode t1 = stack.pop();
            TreeNode t2 = stack.pop();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;

            stack.push(t1.left);
            stack.push(t2.right);
            stack.push(t1.right);
            stack.push(t2.left);
        }
        return true;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}

参考链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-

革命尚未成功，同志仍需努力，冲冲冲

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树