一篇学会二叉树的镜像

本文转载自微信公众号「程序员千羽」，作者程序员千羽。转载本文请联系程序员千羽公众号。

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

 二叉树的镜像

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

    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 ;

递推工作：

初始化节点tmp,用于暂存root的左子节点; .

开启递归右子节点mirrorTree(root.right)，并将返回值作为root的左子节点。

开启递归左子节点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; 
 
 
public class Solution { 
     
    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; 
    } 
 
     
    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为控时跳出;
  • 出栈：记为node ;
  • 添加子节点：将node左和右子节点入栈;
  • 交换：交换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; 
 
 
public class Solution { 
     
    public TreeNode mirrorTree1(TreeNode root) { 
        if (root == null) return null; 
        Stack stack = new Stack() {{ 
            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; 
    } 
     
    public boolean isSymmetric2(TreeNode root) { 
        Stack 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-