【劍指offer】33.二叉樹鏡像

Charles 發布于2019-08-16 13:59 / 1337人閱讀

摘要：題目操作給定的二叉樹，將其變換為源二叉樹的鏡像。再遞歸的對左子樹，以及右子樹進行翻轉。比如左右有一個是代碼執行到交換沒啥問題執行到遞歸，左子樹就結束掉了。

題目

操作給定的二叉樹，將其變換為源二叉樹的鏡像。
二叉樹的鏡像定義：源二叉樹

題解

首先先理解題意,鏡像通過以下幾個步驟可以實現：

可以看到首先對根節點的左右進行翻轉。
再遞歸的對左子樹，以及右子樹進行翻轉。
之前講過，鏈表的題目分為四個步驟：連過來、指針走、斷后路、調狀態。
二涉及到樹的題目，基本都是遞歸。
一旦涉及到遞歸，就要搞清楚兩個東西：

遞歸的過程。在這里就是，先翻轉根節點，再翻轉左子樹，再翻轉右子樹。

遞歸結束的條件。這里就是當樹為Null的時候不翻轉。

public class Solution {
    public void Mirror(TreeNode root) {
        // 遞歸結束條件 
        if (root == null)  return;
        // 交換左右
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 遞歸
        Mirror(root.left);
        Mirror(root.right);
    }
}

同時一般，我們會有一些邊界case去檢查一下代碼的魯棒性。
比如左右有一個是null

代碼執行到交換沒啥問題：

執行到遞歸，左子樹就結束掉了。
右子樹的話還要遞歸的執行左右子樹，也可以執行正確，但是其實沒必要。

public class Solution {
    public void Mirror(TreeNode root) {
        // 遞歸結束條件 
        if (root == null)  return;
        if (roo.left == null && root.left == null) return;
        // 交換左右
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 遞歸
        Mirror(root.left);
        Mirror(root.right);
    }
}

熱門閱讀

【Leetcode】175. 組合兩個表

jvm類加載機制

學習資料推薦

云服務器 GPU云服務器二叉樹 python二叉樹平衡二叉樹實現二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72689.html

【劍指offer】5.二叉樹的鏡像和打印

摘要：題目二叉樹的鏡像題目描述操作給定的二叉樹，將其變換為源二叉樹的鏡像。代碼題目從上往下打印二叉樹題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。解題思路借助隊列先進先出的數據結構讓二叉樹每層依次進入隊列依次打印隊列中的值代碼二叉樹簡介基本結構： function TreeNode(x) { this.val = x; this.left = null; ...

villainhr 2019-08-23 14:43 評論0 收藏0
PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。開篇以下內容可能偏應試但很好理解，所以大家一定要堅持看下去，因為我們變強的過程注定孤獨的，堅持下來就會看到明天的太陽。回顧 showImg(https://user-...

li21 2019-07-01 10:26 評論0 收藏0