Binary Tree Upside Down LC解題記錄

Shonim 發(fā)布于2019-08-14 14:21 / 2684人閱讀

摘要：題目內容因為這道題被鎖住了，在寫這篇文章時還有天就要過期了，把原題也貼上來。題目要求，樹的結構是每個當右邊子節(jié)點的，它肯定有個，就是它的根節(jié)點肯定有個左邊子節(jié)點，也就是說它是二胎。遞歸設置終止條件，在空節(jié)點或最左邊的葉子處終止。

題目內容

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

（因為這道題被鎖住了，在寫這篇文章時還有23天就要過期了，把原題也貼上來。）題目要求，樹的結構是每個當右邊子節(jié)點的，它肯定有個sibling，就是它的根節(jié)點肯定有個左邊子節(jié)點，也就是說它是二胎。現(xiàn)在要把這個樹從右往左看，要返回新的樹。

解決思路

這道題有點兒類似反轉鏈表，所以需要逐個修改每個節(jié)點的指向，以前的爺爺可能就是明天的孫子，曾經(jīng)在工科專業(yè)成績優(yōu)秀轉到CS重頭再來也是這個心情。再仔細看，對于1->2->4，想逆轉成4->2->1，其實就是左<-根->右變成了右<-左->根，好的辦法是先找到左，然后開倒車，想辦法把根和右的關系調整過來。
所以這道題用到自下而上遞歸的辦法，先找到最左邊的葉子，作為新的root，然后給新的root分配好它的left，right child。比如這個例子，先搞清楚4，5，2三個節(jié)點的關系，然后再向上找，搞1，2，3之間的關系。

兩個需要注意的地方，一個是如何高效的找到4，也就是最左邊的葉子。利用好遞歸方法的返回值，總會返回最小規(guī)模問題的返回值，也就是說，當遞歸終止時的返回值就是整個遞歸方法的返回值，之前這句話講的很繞，我自己也在理解中。
第二，注意把原來根節(jié)點和兩個子節(jié)點的指針刪掉，因為最后原來的根節(jié)點一定會被變成一個葉子節(jié)點，那么葉子節(jié)點還指著根節(jié)點的話，就是個漂亮的環(huán)，會出現(xiàn)stackoverflow的錯誤。

code

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        //遞歸設置終止條件，在空節(jié)點或最左邊的葉子處終止。
        if(root == null || (root.left == null && root.right == null)) return root;
        //把最左邊的葉子拎出來作為新的root，留著返回
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        //改各個節(jié)點之間的關系
        root.left.left = root.right;
        root.left.right = root;
        //這步非常有必要，每次改完之后把原來的節(jié)點關系都清空，否則成環(huán)
        root.left = null;
        root.right = null;
        
        return newRoot;
    }
}

復雜度分析

程序遍歷了所有的節(jié)點，而且每個節(jié)點算是遍歷兩次，一次從上到下，一次從下到上。復雜度是O(n)。

云服務器 GPU云服務器 binary-tree binary-search-tree Upside 解題思路

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

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

LeetCode 156 Binary Tree Upside Down 上下翻轉二叉樹

摘要：翻轉以后如下解題思路翻轉的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋。看例子，樹的左邊最深的底層是，是新的。對于每個，將鏈接右孩子的指針去掉，將變?yōu)楫斍白蠛⒆拥模蔀樽蠛⒆拥摹＿f歸的寫法遞歸調用得到新的，并且沿途改變結構。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 評論0 收藏0
Strobogrammatic Number 系列 LC解題記錄（未完成）

摘要：所以這題先建立一個對應的，然后掃一遍字符串就可以了。復雜度分析第二題題目內容解決思路一看關鍵詞，通常都是，深搜一遍，挖地三尺，雁過拔毛。復雜度分析第三題題目內容解決思路復雜度分析該系列共三道題，Company Tag只有一個Google，那就必須要做了。第一題題目內容 A strobogrammatic number is a number that looks the same ...

王晗 2019-08-14 14:23 評論0 收藏0
[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解題思路用遞歸實現(xiàn)很簡單，對于每個根節(jié)點，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點在于如果某個根節(jié)點有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 評論0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉樹最大深度

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 ...

PiscesYE 2019-08-16 13:28 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節(jié)點，或者只有一個子樹。思想來自于的代碼實現(xiàn)。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0