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

mikyou 發(fā)布于2019-08-14 12:32 / 2393人閱讀

摘要：棧法復(fù)雜度時(shí)間空間思路對于一個(gè)根節(jié)點(diǎn)，我們將它的右子樹壓進(jìn)一個(gè)棧中，然后將它的左子樹放到右邊來。如果該節(jié)點(diǎn)沒有左子樹，說明該節(jié)點(diǎn)是某個(gè)左子樹的最后一個(gè)節(jié)點(diǎn)，我們這時(shí)候把棧中最近的右子樹出來接到它的右邊。

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:

棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

對于一個(gè)根節(jié)點(diǎn)，我們將它的右子樹壓進(jìn)一個(gè)棧中，然后將它的左子樹放到右邊來。如果該節(jié)點(diǎn)沒有左子樹，說明該節(jié)點(diǎn)是某個(gè)左子樹的最后一個(gè)節(jié)點(diǎn)，我們這時(shí)候把棧中最近的右子樹pop出來接到它的右邊。

代碼

public class Solution {
    public void flatten(TreeNode root) {
        Stack stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.empty()){
            // 如果有右子樹，先壓入棧，等待遇到當(dāng)前節(jié)點(diǎn)左子樹盡頭的時(shí)候再pop出來
            if(p.right != null){
                stack.push(p.right);
            }
            // 如果存在左子樹，將它放到右邊來
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            // 否則，說明是某個(gè)左子樹的盡頭，就將最近的右子樹接到右邊來
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
            // 移動(dòng)到下一個(gè)待flat節(jié)點(diǎn)
            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ù)雜度

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

思路

如果我們將根節(jié)點(diǎn)的右子樹接到左子樹最后一個(gè)節(jié)點(diǎn)（就是左子樹盡可能靠右下的節(jié)點(diǎn)）的右邊，那我們可以確定的是，該根節(jié)點(diǎn)是已經(jīng)flat的了。執(zhí)行完該鏈接操作，根節(jié)點(diǎn)就只有右子樹了，這樣我們再移動(dòng)到右子樹的根節(jié)點(diǎn)，反復(fù)執(zhí)行同樣的操作，每次保證一個(gè)節(jié)點(diǎn)被flat。

代碼

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