[Leetcode] Flatten Binary Tree to Linked List 整平二叉

mikyou 發布于2019-08-14 12:32 / 2392人閱讀

摘要：棧法復雜度時間空間思路對于一個根節點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節點沒有左子樹，說明該節點是某個左子樹的最后一個節點，我們這時候把棧中最近的右子樹出來接到它的右邊。

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, Given

The flattened tree should look like:

棧法 復雜度

時間 O(N) 空間 O(N)

思路

對于一個根節點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節點沒有左子樹，說明該節點是某個左子樹的最后一個節點，我們這時候把棧中最近的右子樹pop出來接到它的右邊。

代碼

public class Solution {
    public void flatten(TreeNode root) {
        Stack stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.empty()){
            // 如果有右子樹，先壓入棧，等待遇到當前節點左子樹盡頭的時候再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節點
            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
    }
}

鏈接左右子樹法 復雜度

時間 O(N) 空間 O(1)

思路

如果我們將根節點的右子樹接到左子樹最后一個節點（就是左子樹盡可能靠右下的節點）的右邊，那我們可以確定的是，該根節點是已經flat的了。執行完該鏈接操作，根節點就只有右子樹了，這樣我們再移動到右子樹的根節點，反復執行同樣的操作，每次保證一個節點被flat。

代碼

public class Solution {
    public void flatten(TreeNode root) {
        while(root != null){
            // 當存在左子樹時，說明該節點還沒被flat
            if(root.left != null){
                // 找到左子樹最后一個節點
                TreeNode endOfLeftSubTree = root.left;
                while(endOfLeftSubTree.right != null){
                    endOfLeftSubTree = endOfLeftSubTree.right;
                }
                // 將右子樹加到左子樹最后一個節點的右邊
                endOfLeftSubTree.right = root.right;
                // 將左子樹放到當前節點的右邊
                root.right = root.left;
                // 將當前節點左邊置空
                root.left = null;
            }
            // 移動到下一個待flat的節點
            root = root.right;
        }
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Flatten linked

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

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

leetcode114. Flatten Binary Tree to Linked List

摘要：題目要求將一棵二叉樹展開形成一棵鏈表形狀的樹。本質上是將該樹轉變成先序遍歷后的樣子。所以這個例題一步步的操作如下代碼如下思路二遞歸其實這里的思路等價于反轉的先序遍歷。自底向上深度優先遍歷，這要求將前序遍歷的頭結點通過臨時變量保存一下。題目要求 Given a binary tree, flatten it to a linked list in-place. For example...

zhjx922 2019-08-15 11:07 評論0 收藏0
[LeetCode] Flatten Binary Tree to Linked List

摘要：思路這題相當于是當的時候，關鍵是要知道要被連接的的前面的一個這樣才可以把接上。用一路做到底，當做到的時候，左邊返回右邊也返回，這時返回自己成為同樣接著繼續做。 Flatten Binary Tree to Linked List Flatten a binary tree to a fake linked list in pre-order traversal.Here we use ...

lowett 2019-08-16 10:34 評論0 收藏0
[LintCode/LeetCode] Flatten Binary Tree to Linked

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

TNFE 2019-08-14 15:12 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0