資訊專欄INFORMATION COLUMN
摘要：題目?jī)?nèi)容因?yàn)檫@道題被鎖住了，在寫這篇文章時(shí)還有天就要過期了，把原題也貼上來。題目要求，樹的結(jié)構(gòu)是每個(gè)當(dāng)右邊子節(jié)點(diǎn)的，它肯定有個(gè)，就是它的根節(jié)點(diǎn)肯定有個(gè)左邊子節(jié)點(diǎn)，也就是說它是二胎。遞歸設(shè)置終止條件，在空節(jié)點(diǎn)或最左邊的葉子處終止。
題目?jī)?nèi)容
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5},
1
/
2 3
/
4 5
return the root of the binary tree [4,5,2,null,null,3,1].
4
/
5 2
/
3 1
（因?yàn)檫@道題被鎖住了，在寫這篇文章時(shí)還有23天就要過期了，把原題也貼上來。）題目要求，樹的結(jié)構(gòu)是每個(gè)當(dāng)右邊子節(jié)點(diǎn)的，它肯定有個(gè)sibling，就是它的根節(jié)點(diǎn)肯定有個(gè)左邊子節(jié)點(diǎn)，也就是說它是二胎?，F(xiàn)在要把這個(gè)樹從右往左看，要返回新的樹。
解決思路這道題有點(diǎn)兒類似反轉(zhuǎn)鏈表，所以需要逐個(gè)修改每個(gè)節(jié)點(diǎn)的指向，以前的爺爺可能就是明天的孫子，曾經(jīng)在工科專業(yè)成績(jī)優(yōu)秀轉(zhuǎn)到CS重頭再來也是這個(gè)心情。再仔細(xì)看，對(duì)于1->2->4，想逆轉(zhuǎn)成4->2->1，其實(shí)就是左<-根->右變成了右<-左->根，好的辦法是先找到左，然后開倒車，想辦法把根和右的關(guān)系調(diào)整過來。
所以這道題用到自下而上遞歸的辦法，先找到最左邊的葉子，作為新的root，然后給新的root分配好它的left，right child。比如這個(gè)例子，先搞清楚4，5，2三個(gè)節(jié)點(diǎn)的關(guān)系，然后再向上找，搞1，2，3之間的關(guān)系。
兩個(gè)需要注意的地方，一個(gè)是如何高效的找到4，也就是最左邊的葉子。利用好遞歸方法的返回值，總會(huì)返回最小規(guī)模問題的返回值，也就是說，當(dāng)遞歸終止時(shí)的返回值就是整個(gè)遞歸方法的返回值，之前這句話講的很繞，我自己也在理解中。
第二，注意把原來根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)的指針刪掉，因?yàn)樽詈笤瓉淼母?jié)點(diǎn)一定會(huì)被變成一個(gè)葉子節(jié)點(diǎn)，那么葉子節(jié)點(diǎn)還指著根節(jié)點(diǎn)的話，就是個(gè)漂亮的環(huán)，會(huì)出現(xiàn)stackoverflow的錯(cuò)誤。
public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
//遞歸設(shè)置終止條件，在空節(jié)點(diǎn)或最左邊的葉子處終止。
if(root == null || (root.left == null && root.right == null)) return root;
//把最左邊的葉子拎出來作為新的root，留著返回
TreeNode newRoot = upsideDownBinaryTree(root.left);
//改各個(gè)節(jié)點(diǎn)之間的關(guān)系
root.left.left = root.right;
root.left.right = root;
//這步非常有必要，每次改完之后把原來的節(jié)點(diǎn)關(guān)系都清空，否則成環(huán)
root.left = null;
root.right = null;
return newRoot;
}
}
復(fù)雜度分析
程序遍歷了所有的節(jié)點(diǎn)，而且每個(gè)節(jié)點(diǎn)算是遍歷兩次，一次從上到下，一次從下到上。復(fù)雜度是O(n)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64962.html
摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開始不是很清楚，但是里面的高票答案給了一個(gè)很好的解釋。看例子，樹的左邊最深的底層是，是新的。對(duì)于每個(gè)，將鏈接右孩子的指針去掉，將變?yōu)楫?dāng)前左孩子的，成為左孩子的。遞歸的寫法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...
摘要：所以這題先建立一個(gè)對(duì)應(yīng)的，然后掃一遍字符串就可以了。復(fù)雜度分析第二題題目?jī)?nèi)容解決思路一看關(guān)鍵詞，通常都是，深搜一遍，挖地三尺，雁過拔毛。復(fù)雜度分析第三題題目?jī)?nèi)容解決思路復(fù)雜度分析 該系列共三道題，Company Tag只有一個(gè)Google，那就必須要做了。 第一題題目?jī)?nèi)容 A strobogrammatic number is a number that looks the same ...
摘要：解題思路用遞歸實(shí)現(xiàn)很簡(jiǎn)單，對(duì)于每個(gè)根節(jié)點(diǎn)，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點(diǎn)在于如果某個(gè)根節(jié)點(diǎn)有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...
LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...
摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來，最后回原來正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。思想來自于的代碼實(shí)現(xiàn)。 跳過總結(jié)請(qǐng)點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.v...
閱讀 1040·2021-11-24 10:30
閱讀 2371·2021-10-08 10:04
閱讀 4029·2021-09-30 09:47
閱讀 1512·2021-09-29 09:45
閱讀 1491·2021-09-24 10:33
閱讀 6336·2021-09-22 15:57
閱讀 2391·2021-09-22 15:50
閱讀 4126·2021-08-30 09:45
