[[437293]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員千羽」，作者程序員千羽。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員千羽公眾號(hào)。

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

 二叉樹的鏡像

“題目描述 ：請(qǐng)完成一個(gè)函數(shù)，輸入一個(gè)二叉樹，該函數(shù)輸出它的鏡像。例如輸入：

    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 <= 節(jié)點(diǎn)個(gè)數(shù) <= 1000

分析

二叉樹鏡像定義： 對(duì)于二叉樹中任意節(jié)點(diǎn) root ，設(shè)其左 / 右子節(jié)點(diǎn)分別為 left, right;則在二叉樹的鏡像中的對(duì)應(yīng) root節(jié)點(diǎn)，其左 / 右子節(jié)點(diǎn)分別為 right, left 。

方法一：遞歸法

根據(jù)二叉樹鏡像的定義，考慮遞歸遍歷(dfs)二叉樹，交換每個(gè)節(jié)點(diǎn)的左 / 右子節(jié)點(diǎn)，即可生成二叉樹的鏡像。

遞歸解析：

終止條件： 當(dāng)節(jié)點(diǎn) root為空時(shí)(即越過葉節(jié)點(diǎn))，則返回 null ;

遞推工作：

初始化節(jié)點(diǎn)tmp,用于暫存root的左子節(jié)點(diǎn); .

開啟遞歸右子節(jié)點(diǎn)mirrorTree(root.right)，并將返回值作為root的左子節(jié)點(diǎn)。

開啟遞歸左子節(jié)點(diǎn)mirrorTree(tmp) ,并將返回值作為root的右子節(jié)點(diǎn)。

返回值:返回當(dāng)前節(jié)點(diǎn)root ;

“Q:為何需要暫存root的左子節(jié)點(diǎn)? A:在遞歸右子節(jié) 點(diǎn)“root.left = mirrorTree(root.right);"執(zhí)行完畢后，root.left 的值已經(jīng)發(fā)生改變,此時(shí)遞歸左子節(jié)點(diǎn)mirrorTree(root.left)則會(huì)出問題。

復(fù)雜度分析:

• 時(shí)間復(fù)雜度0(N) ： 其中N為二叉樹的節(jié)點(diǎn)數(shù)量，建立二叉樹鏡像需要遍歷樹的所有節(jié)點(diǎn)，占用O(N)時(shí)間。
• 空間復(fù)雜度O(N)： 最差情況下(當(dāng)二叉樹退化為鏈表)，遞歸時(shí)系統(tǒng)需使用O(N)大小的棧空間。

package com.nateshao.sword_offer.topic_21_mirrorTree; 
 
import java.util.Stack; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/24 22:48 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 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; 
    } 
 
    /** 
     * 解法一：遞歸，時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：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; 
        } 
    } 
 
} 

方法二：輔助棧(或隊(duì)列)

利用棧(或隊(duì)列)遍歷樹的所有節(jié)點(diǎn)node，并交換每個(gè)node的左/右子節(jié)點(diǎn)。

算法流程：

• 特例處理： 當(dāng)root為空時(shí)，直接返回null ;
• 初始化： 棧(或隊(duì)列)，本文用棧，并加入根節(jié)點(diǎn)root 。
• 循環(huán)交換： 當(dāng)棧 stack為控時(shí)跳出;
  • 出棧：記為node ;
  • 添加子節(jié)點(diǎn)：將node左和右子節(jié)點(diǎn)入棧;
  • 交換：交換node的左1右子節(jié)點(diǎn)。
• 返回值：返回根節(jié)點(diǎn)root。

復(fù)雜度分析:

• 時(shí)間復(fù)雜度0(N) ：其中N為二叉樹的節(jié)點(diǎn)數(shù)量，建立二叉樹鏡像需要遍歷樹的所有節(jié)點(diǎn)，占用O(N)時(shí)間。
• 空間復(fù)雜度O(N) ：如下圖所示,最差情況下，棧stack最多同時(shí)存儲(chǔ)N+1/2個(gè)節(jié)點(diǎn)，占用O(N)額外空間。

package com.nateshao.sword_offer.topic_21_mirrorTree; 
 
import java.util.Stack; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/24 22:48 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 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; 
    } 
    /** 
     * 解法二：迭代，時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：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-