資訊專欄INFORMATION COLUMN
摘要：題目操作給定的二叉樹，將其變換為源二叉樹的鏡像。再遞歸的對左子樹，以及右子樹進(jìn)行翻轉(zhuǎn)。比如左右有一個是代碼執(zhí)行到交換沒啥問題執(zhí)行到遞歸，左子樹就結(jié)束掉了。
題目
操作給定的二叉樹，將其變換為源二叉樹的鏡像。
二叉樹的鏡像定義：源二叉樹
8
/
6 10
/ /
5 7 9 11
鏡像二叉樹
8
/
10 6
/ /
11 9 7 5
題解
首先先理解題意,鏡像通過以下幾個步驟可以實(shí)現(xiàn)：
可以看到首先對根節(jié)點(diǎn)的左右進(jìn)行翻轉(zhuǎn)。
再遞歸的對左子樹，以及右子樹進(jìn)行翻轉(zhuǎn)。
之前講過，鏈表的題目分為四個步驟：連過來、指針走、斷后路、調(diào)狀態(tài)。
二涉及到樹的題目，基本都是遞歸。
一旦涉及到遞歸，就要搞清楚兩個東西：
遞歸的過程。在這里就是，先翻轉(zhuǎn)根節(jié)點(diǎn)，再翻轉(zhuǎn)左子樹，再翻轉(zhuǎn)右子樹。
遞歸結(jié)束的條件。 這里就是當(dāng)樹為Null的時候不翻轉(zhuǎn)。
public class Solution {
public void Mirror(TreeNode root) {
// 遞歸結(jié)束條件
if (root == null) return;
// 交換左右
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 遞歸
Mirror(root.left);
Mirror(root.right);
}
}
同時一般，我們會有一些邊界case去檢查一下代碼的魯棒性。
比如左右有一個是null
8
/
10 Null
/
null null
代碼執(zhí)行到交換沒啥問題：
8
/
Null 10
/
null null
執(zhí)行到遞歸，左子樹就結(jié)束掉了。
右子樹的話還要遞歸的執(zhí)行左右子樹，也可以執(zhí)行正確，但是其實(shí)沒必要。
public class Solution {
public void Mirror(TreeNode root) {
// 遞歸結(jié)束條件
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類加載機(jī)制
學(xué)習(xí)資料推薦
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/72689.html
摘要：題目二叉樹的鏡像題目描述操作給定的二叉樹，將其變換為源二叉樹的鏡像。代碼題目從上往下打印二叉樹題目描述從上往下打印出二叉樹的每個節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。解題思路借助隊列先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)讓二叉樹每層依次進(jìn)入隊列依次打印隊列中的值代碼 二叉樹簡介 基本結(jié)構(gòu)： function TreeNode(x) { this.val = x; this.left = null; ...
摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運(yùn)用了二叉樹先序中序遍歷算法。 開篇 以下內(nèi)容可能偏應(yīng)試但很好理解，所以大家一定要堅持看下去，因?yàn)槲覀冏儚?qiáng)的過程注定孤獨(dú)的，堅持下來就會看到明天的太陽。 回顧 showImg(https://user-...
閱讀 2885·2023-04-25 23:08
閱讀 1697·2021-11-23 09:51
閱讀 1696·2021-10-27 14:18
閱讀 3173·2019-08-29 13:25
閱讀 2895·2019-08-29 13:14
閱讀 3036·2019-08-26 18:36
閱讀 2260·2019-08-26 12:11
閱讀 874·2019-08-26 11:29
