資訊專欄INFORMATION COLUMN
摘要：棧法復(fù)雜度時間空間思路對于一個根節(jié)點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節(jié)點沒有左子樹，說明該節(jié)點是某個左子樹的最后一個節(jié)點，我們這時候把棧中最近的右子樹出來接到它的右邊。
Flatten Binary Tree to Linked List
棧法 復(fù)雜度Given a binary tree, flatten it to a linked list in-place.
For example, Given
1 / 2 5 / 3 4 6The flattened tree should look like:
1 2 3 4 5 6
時間 O(N) 空間 O(N)
思路對于一個根節(jié)點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節(jié)點沒有左子樹，說明該節(jié)點是某個左子樹的最后一個節(jié)點，我們這時候把棧中最近的右子樹pop出來接到它的右邊。
代碼public class Solution {
public void flatten(TreeNode root) {
Stack stack = new Stack();
TreeNode p = root;
while(p != null || !stack.empty()){
// 如果有右子樹，先壓入棧，等待遇到當(dāng)前節(jié)點左子樹盡頭的時候再pop出來
if(p.right != null){
stack.push(p.right);
}
// 如果存在左子樹，將它放到右邊來
if(p.left != null){
p.right = p.left;
p.left = null;
// 否則，說明是某個左子樹的盡頭，就將最近的右子樹接到右邊來
}else if(!stack.empty()){
TreeNode temp = stack.pop();
p.right=temp;
}
// 移動到下一個待flat節(jié)點
p = p.right;
}
}
}
2018/2
class Solution:
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
stack = []
currentNode = root
while currentNode is not None:
if currentNode.right is not None:
stack.append(currentNode.right)
if currentNode.left is not None:
currentNode.right = currentNode.left
currentNode.left = None
elif stack:
currentNode.right = stack.pop()
currentNode = currentNode.right
2018/10
func flatten(root *TreeNode) {
if root == nil {
return
}
stack := []*TreeNode{root}
curr := &TreeNode{0, nil, nil}
for len(stack) != 0 {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// DFS from left to right, push right to the stack first
if top.Right != nil {
stack = append(stack, top.Right)
}
// push left to the stack
if top.Left != nil {
stack = append(stack, top.Left)
}
// put top to curr"s right and clear curr"s left
curr.Left = nil
curr.Right = top
// move on to the next
curr = curr.Right
}
}
鏈接左右子樹法
復(fù)雜度
時間 O(N) 空間 O(1)
思路如果我們將根節(jié)點的右子樹接到左子樹最后一個節(jié)點（就是左子樹盡可能靠右下的節(jié)點）的右邊，那我們可以確定的是，該根節(jié)點是已經(jīng)flat的了。執(zhí)行完該鏈接操作，根節(jié)點就只有右子樹了，這樣我們再移動到右子樹的根節(jié)點，反復(fù)執(zhí)行同樣的操作，每次保證一個節(jié)點被flat。
代碼public class Solution {
public void flatten(TreeNode root) {
while(root != null){
// 當(dāng)存在左子樹時，說明該節(jié)點還沒被flat
if(root.left != null){
// 找到左子樹最后一個節(jié)點
TreeNode endOfLeftSubTree = root.left;
while(endOfLeftSubTree.right != null){
endOfLeftSubTree = endOfLeftSubTree.right;
}
// 將右子樹加到左子樹最后一個節(jié)點的右邊
endOfLeftSubTree.right = root.right;
// 將左子樹放到當(dāng)前節(jié)點的右邊
root.right = root.left;
// 將當(dāng)前節(jié)點左邊置空
root.left = null;
}
// 移動到下一個待flat的節(jié)點
root = root.right;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64542.html
摘要：題目要求將一棵二叉樹展開形成一棵鏈表形狀的樹。本質(zhì)上是將該樹轉(zhuǎn)變成先序遍歷后的樣子。所以這個例題一步步的操作如下代碼如下思路二遞歸其實這里的思路等價于反轉(zhuǎn)的先序遍歷。自底向上深度優(yōu)先遍歷，這要求將前序遍歷的頭結(jié)點通過臨時變量保存一下。 題目要求 Given a binary tree, flatten it to a linked list in-place. For example...
摘要：思路這題相當(dāng)于是當(dāng)?shù)臅r候，關(guān)鍵是要知道要被連接的的前面的一個這樣才可以把接上。用一路做到底，當(dāng)做到的時候，左邊返回右邊也返回，這時返回自己成為同樣接著繼續(xù)做。 Flatten Binary Tree to Linked List Flatten a binary tree to a fake linked list in pre-order traversal.Here we use ...
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)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 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ū)別...
閱讀 3752·2021-10-09 09:44
閱讀 3510·2021-09-22 15:29
閱讀 3297·2019-08-30 15:54
閱讀 3077·2019-08-29 16:19
閱讀 2224·2019-08-29 12:50
閱讀 648·2019-08-26 14:04
閱讀 1777·2019-08-23 18:39
閱讀 1403·2019-08-23 17:59
