資訊專欄INFORMATION COLUMN
摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋。看例子，樹的左邊最深的底層是，是新的。對于每個，將鏈接右孩子的指針去掉，將變?yōu)楫?dāng)前左孩子的，成為左孩子的。遞歸的寫法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。
LeetCode 156 Binary Tree Upside Down
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.
Example:
Input: [1,2,3,4,5]
1 / 2 3 / 4 5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
翻轉(zhuǎn)以后如下：
4
/
5 2
/
3 1
解題思路：
翻轉(zhuǎn)的形式一開始不是很清楚，但是discuss里面的高票答案給了一個很好的解釋?？蠢?，樹的左邊最深的底層是4，4是新的root。對于每個root node，將鏈接右孩子的指針去掉，將root node變?yōu)楫?dāng)前左孩子的left node，root node成為左孩子的right node。
1 / x 2 -- 3 / x 4 -- 5 ^ new root
遞歸的寫法：
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null || root.left == null) {
return root;
}
//遞歸調(diào)用得到新的root，并且沿途改變結(jié)構(gòu)。
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right;
root.left.right = root;
//千萬記得將root node 的左右兩邊設(shè)為null
root.left = null;
root.right = null;
return newRoot;
}
遍歷的解法
遍歷的解法需要四個指針，如圖所示，每次先update next，然后對swap上一個node的右孩子和這個node的左孩子，所以每次我們需要一個temp來記錄上一個node的右邊孩子。
prev -> 1
/ x
curr -> 2 -- 3 <-temp
/ x
next-> 4 -- 5
^
new root
代碼如下
public TreeNode upsideDownBinaryTree(TreeNode root) {
//iterative
TreeNode curr = root;
TreeNode prev = null;
TreeNode next = null;
TreeNode temp = null;
while(curr != null) {
next = curr.left;
//swap nodes, we need to keep a temp to track the right node
curr.left = temp;
temp = curr.right;
curr.right = prev;
prev = curr;
curr = next;
}
return prev;
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71794.html
摘要：原題鏈接遞歸法復(fù)雜度時間空間遞歸?？臻g思路這個難倒大神的題也是非常經(jīng)典的一道測試對二叉樹遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點或葉子節(jié)點時，不再交換，直接返回該節(jié)點。代碼給出的是后序遍歷的自下而上的交換，先序遍歷的話就是自上而下的交換。 Invert Binary Tree Invert a binary tree. 4 / 2 7 / ...
摘要：算法思路判斷樹是否為空同時也是終止條件。分別對左右子樹進行遞歸。代碼實現(xiàn)判斷當(dāng)前樹是否為左右子樹結(jié)點交換分別對左右子樹進行遞歸返回樹的根節(jié)點歡迎一起加入到開源倉庫，可以向提交您其他語言的代碼。 Time：2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿 題目：Invert Binary Tree（反轉(zhuǎn)二叉樹） ...
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 ...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
閱讀 1973·2021-11-19 09:40
閱讀 2169·2021-10-09 09:43
閱讀 3307·2021-09-06 15:00
閱讀 2826·2019-08-29 13:04
閱讀 2780·2019-08-26 11:53
閱讀 3546·2019-08-26 11:46
閱讀 2335·2019-08-26 11:38
閱讀 406·2019-08-26 11:27
