資訊專欄INFORMATION COLUMN
摘要：題目要求將一棵二叉樹展開形成一棵鏈表形狀的樹。本質(zhì)上是將該樹轉(zhuǎn)變成先序遍歷后的樣子。所以這個例題一步步的操作如下代碼如下思路二遞歸其實這里的思路等價于反轉(zhuǎn)的先序遍歷。自底向上深度優(yōu)先遍歷，這要求將前序遍歷的頭結(jié)點通過臨時變量保存一下。
題目要求
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/
2 5
/
3 4 6
The flattened tree should look like:
1
2
3
4
5
6
click to show hints.
Hints:
If you notice carefully in the flattened tree, each node"s right child points to the next node of a pre-order traversal.
將一棵二叉樹展開形成一棵鏈表形狀的樹。本質(zhì)上是將該樹轉(zhuǎn)變成先序遍歷后的樣子。
思路一：非遞歸如果我們從圖形的角度來說，每一次都將當前節(jié)點的右子樹拼接到左子節(jié)點的右子樹下，再將左節(jié)點替換原來的右節(jié)點。所以這個例題一步步的操作如下：
1 1 1
/
2 5 2 2
/ /
3 4 6 3 4 3
5 4
6 5
6
代碼如下：
public void flatten(TreeNode root) {
if(root==null) return;
TreeNode temp = root;
TreeNode current = root;
while(current!=null){
if(current.left!=null){
temp = current.left;
while(temp.right!=null) temp = temp.right;
temp.right = current.right;
current.right = current.left;
current.left = null;
}
current = current.right;
}
}
思路二：遞歸
其實這里的思路等價于反轉(zhuǎn)的先序遍歷。自底向上深度優(yōu)先遍歷，這要求將前序遍歷的頭結(jié)點通過臨時變量保存一下。代碼如下：
TreeNode pre = null;
public void flatten2(TreeNode root) {
if(root==null) return;
flatten(root.right);
flatten(root.left);
root.left = null;
root.right = pre;
pre = root;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67556.html
摘要：思路這題相當于是當?shù)臅r候，關(guān)鍵是要知道要被連接的的前面的一個這樣才可以把接上。用一路做到底，當做到的時候，左邊返回右邊也返回，這時返回自己成為同樣接著繼續(xù)做。 Flatten Binary Tree to Linked List Flatten a binary tree to a fake linked list in pre-order traversal.Here we use ...
摘要：棧法復雜度時間空間思路對于一個根節(jié)點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節(jié)點沒有左子樹，說明該節(jié)點是某個左子樹的最后一個節(jié)點，我們這時候把棧中最近的右子樹出來接到它的右邊。 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-plac...
Problem Flatten a binary tree to a fake linked list in pre-order traversal.Here we use the right pointer in TreeNode as the next pointer in ListNode. Example 1 1 ...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 3210·2021-11-10 11:36
閱讀 3155·2021-11-02 14:39
閱讀 1737·2021-09-26 10:11
閱讀 4975·2021-09-22 15:57
閱讀 1697·2021-09-09 11:36
閱讀 2057·2019-08-30 12:56
閱讀 3497·2019-08-30 11:17
閱讀 1707·2019-08-29 17:17
