[Leetcode解題] Flatten Binary Tree to Linked List - 遍歷二叉樹

11 February 2022
medium tree linked-list

題目

114. Flatten Binary Tree to Linked List

給一個二叉樹的root，將樹壓平成一個linked list。 這個linked list應該與二叉樹的前序遍歷順序相同。

解法一

解題思路

從這棵樹的前序遍歷最遠的Node開始(下圖中的6)

graphviz-4b44a5cd981c0641948c69f8262e6d76 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] //node [label=1 fillcolor="#cce8ff"] 1.1 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [ label="\N"] 1 -> 2 -> 3 2 -> 4 1 -> 5 -> null 5 -> 6 } 1 1 2 2 1->2 5 5 1->5 3 3 2->3 4 4 2->4 null null 5->null 6 6 5->6

將這個Node(下圖中的6)的指標存到pre

graphviz-61704b33716b9120e40b9908c130e2dc digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [ label="\N"] pre -> 6 } pre pre 6 6 pre->6
graphviz-53e5e49bc374b52187ef4122582488fa digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 //node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 2 -> 4 1 -> 5 -> n1 5 -> 6 } 1 1 2 2 1->2 5 5 1->5 3 3 2->3 4 4 2->4 n1 null 5->n1 6 6 5->6

不是pre的child且前序遍歷最遠的Node(下圖中的5)的left設為NULL，並將上一步的pre接到Node(下圖中的5)的right，將pre設為Node(下圖中的5)

graphviz-1626216c2fea5424cb8375fa37b705c6 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [label=5 fillcolor=lightgray] 5 node [ label="\N"] pre -> 5 -> 6 } pre pre 5 5 pre->5 6 6 5->6
graphviz-53e5e49bc374b52187ef4122582488fa digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 //node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 2 -> 4 1 -> 5 -> n1 5 -> 6 } 1 1 2 2 1->2 5 5 1->5 3 3 2->3 4 4 2->4 n1 null 5->n1 6 6 5->6

不是pre的child且前序遍歷最遠的Node(下圖中的4)的left設為NULL，並將上一步的pre接到Node(下圖中的4)的right，將pre設為Node(下圖中的4)

graphviz-ff8e1773c7e521ee231d3258d6f4ecc8 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [label=5 fillcolor=lightgray] 5 node [label=4 fillcolor=lightgray] 4 node [ label="\N"] pre -> 4 -> 5 -> 6 } pre pre 4 4 pre->4 6 6 5 5 5->6 4->5
graphviz-51c427b837c0ac62a793f8abe5856b5a digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 2 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 } n2 null n3 null 1 1 2 2 1->2 n1 null 1->n1 3 3 2->3 4 4 2->4 4->n2 5 5 4->5 5->n3 6 6 5->6

依此類推…

graphviz-a7a4479ddafc3155fa302799e369357e digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [label=5 fillcolor=lightgray] 5 node [label=4 fillcolor=lightgray] 4 node [label=3 fillcolor=lightgray] 3 node [ label="\N"] pre -> 3 -> 4 -> 5 -> 6 } pre pre 3 3 pre->3 6 6 5 5 5->6 4 4 4->5 3->4
graphviz-7c353766fd503d778564f8ff36a56667 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=null fillcolor=lightgray] n4 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n5 node [ label="\N"] 1 -> 2 -> 3 -> n4 3 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 2 -> n5 } n2 null n3 null n4 null 1 1 2 2 1->2 n1 null 1->n1 3 3 2->3 n5 null 2->n5 3->n4 4 4 3->4 4->n2 5 5 4->5 5->n3 6 6 5->6

依此類推…

graphviz-db5a4fbbfeb58d061f1934ef28b23137 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [label=5 fillcolor=lightgray] 5 node [label=4 fillcolor=lightgray] 4 node [label=3 fillcolor=lightgray] 3 node [label=2 fillcolor=lightgray] 2 node [ label="\N"] pre -> 2 -> 3 -> 4 -> 5 -> 6 } pre pre 2 2 pre->2 6 6 5 5 5->6 4 4 4->5 3 3 3->4 2->3
graphviz-fd3604517dc6820d091e63d6f4092263 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=null fillcolor=lightgray] n4 node [label=null fillcolor=lightgray] n5 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 -> n4 3 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 2 -> n5 } n2 null n3 null n4 null n5 null 1 1 2 2 1->2 n1 null 1->n1 2->n5 3 3 2->3 3->n4 4 4 3->4 4->n2 5 5 4->5 5->n3 6 6 5->6

依此類推…

graphviz-c07b701ff2fe3e059ce554fe0c9eddc4 digraph { rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=pre fillcolor="#cce8ff"] pre node [label=6 fillcolor=lightgray] 6 node [label=5 fillcolor=lightgray] 5 node [label=4 fillcolor=lightgray] 4 node [label=3 fillcolor=lightgray] 3 node [label=2 fillcolor=lightgray] 2 node [label=1 fillcolor=lightgray] 1 node [ label="\N"] pre -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 } pre pre 1 1 pre->1 6 6 5 5 5->6 4 4 4->5 3 3 3->4 2 2 2->3 1->2
graphviz-8a2f61ede13c9a51f9ad53bb0e778bee digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n1 node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=null fillcolor=lightgray] n4 node [label=null fillcolor=lightgray] n5 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 -> n4 3 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 2 -> n5 } n1 null n2 null n3 null n4 null n5 null 1 1 1->n1 2 2 1->2 2->n5 3 3 2->3 3->n4 4 4 3->4 4->n2 5 5 4->5 5->n3 6 6 5->6

實作

  1. 以前序遍歷倒序遞迴的方式去遍歷所有節點 1.1 遞迴遍歷當前節點的右子樹。 1.2 遞迴遍歷當前節點的左子樹。 1.3 訪問當前節點。
  2. 訪問到當前節點時，將當前節點的left設為None, 並將right設為前一次存在pre中的結點
  3. 將當前存在pre(代表已經flatten好的部分)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.pre = None

    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if (not root):
            return
        self.flatten(root.right)
        self.flatten(root.left)
        root.left = None
        root.right = self.pre
        self.pre = root

時間複雜度

由於pre會指到每個節點一次，更新節點狀態的時間複雜度為$O(1)$，圖中有n個節點，時間複雜度為$O(n)$

解法二

解題思路

一開始，我們將指標cr指到root，以下用黃色代表cr cr(節點1)的左邊子樹(淺粉色區域)的root(節點2)，左邊子樹前序遍歷最遠的點(節點4)

graphviz-6ed43fc56a6cc7ed4b0040d0dd0e1ba3 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=1 fillcolor="#ffe66d"] 1 node [label=2 fillcolor="#cce8ff"] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor="#cce8ff"] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 //node [label=null fillcolor=lightgray] n2 node [ label="\N"] graph [style="filled,rounded" fillcolor="#ffdddda7"] subgraph cluster_1 {2 3 4} 1 -> 2 -> 3 2 -> 4 1 -> 5 -> n1 5 -> 6 } cluster_1 1 1 2 2 1->2 5 5 1->5 3 3 2->3 4 4 2->4 n1 null 5->n1 6 6 5->6

將左邊子樹(淺粉色區域)移到cr(節點1)和cr.right(節點5)的中間:

  1. 將cr右側子樹接到前序遍歷最遠的點(節點4)的右側
  2. 將cr左側子樹接到cr右側
graphviz-b2376157d1a8a2d2e4c235de8b901bdc digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=1 fillcolor="#ffe66d"] 1 node [label=2 fillcolor="#cce8ff"] 2 node [label=3 fillcolor=lightgray] 3 node [label=4 fillcolor="#cce8ff"] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 //node [label=null fillcolor=lightgray] n2 node [ label="\N"] graph [style="filled,rounded" fillcolor="#ffdddda7"] subgraph cluster_1 {2 3 4} 1 -> n2 1 -> 2 -> 3 2 -> 4 -> 5 -> n1 4 -> n3 5 -> 6 } cluster_1 n2 null n3 null 1 1 1->n2 2 2 1->2 3 3 2->3 4 4 2->4 4->n3 5 5 4->5 n1 null 5->n1 6 6 5->6

cr向右移動，此時cr為節點2。 cr(節點2)的左邊子樹(淺粉色區域)的root(節點3)，左邊子樹前序遍歷最遠的點(節點3)

graphviz-fe64508bb47196744418f452873de631 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor="#ffe66d"] 2 node [label=3 fillcolor="#cce8ff"] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=null fillcolor=lightgray] n1 node [label=6 fillcolor=lightgray] 6 //node [label=null fillcolor=lightgray] n2 node [ label="\N"] graph [style="filled,rounded" fillcolor="#ffdddda7"] subgraph cluster_1 {3} 1 -> n2 1 -> 2 -> 3 2 -> 4 -> 5 -> n1 4 -> n3 5 -> 6 } cluster_1 n2 null n3 null 1 1 1->n2 2 2 1->2 3 3 2->3 4 4 2->4 4->n3 5 5 4->5 n1 null 5->n1 6 6 5->6

將cr左邊子樹(淺粉色區域)移到cr(節點2)和cr.right(節點4)的中間

graphviz-9a3c11fb9e78f7090049dc928d0c405e digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n1 node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=null fillcolor=lightgray] n4 node [label=null fillcolor=lightgray] n5 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor="#ffe66d"] 2 node [label=3 fillcolor="#cce8ff"] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [ label="\N"] graph [style="filled,rounded" fillcolor="#ffdddda7"] subgraph cluster_1 {3} 1 -> 2 -> 3 -> n4 3 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 2 -> n5 } cluster_1 n1 null n2 null n3 null n4 null n5 null 1 1 1->n1 2 2 1->2 2->n5 3 3 2->3 3->n4 4 4 3->4 4->n2 5 5 4->5 5->n3 6 6 5->6

cr向右移動，此時cr為節點3。 cr的左側為空，不需要做任何事情。 cr持續向右移動，如果cr的左側不為空，按照之前的方式將左側子樹移到cr和cr.right中間

graphviz-cba84a1567864862ec504c0179d37076 digraph { //rankdir=LR ranksep=0.3 node [shape=box style="rounded,filled" height=0.3] node [label=null fillcolor=lightgray] n1 node [label=null fillcolor=lightgray] n2 node [label=null fillcolor=lightgray] n3 node [label=null fillcolor=lightgray] n4 node [label=null fillcolor=lightgray] n5 node [label=1 fillcolor=lightgray] 1 node [label=2 fillcolor=lightgray] 2 node [label=3 fillcolor="#ffe66d"] 3 node [label=4 fillcolor=lightgray] 4 node [label=5 fillcolor=lightgray] 5 node [label=6 fillcolor=lightgray] 6 node [label=null fillcolor=lightgray] n2 node [ label="\N"] 1 -> 2 -> 3 -> n4 3 -> 4 ->5 -> 6 1 -> n1 4 -> n2 5 -> n3 2 -> n5 } n1 null n2 null n3 null n4 null n5 null 1 1 1->n1 2 2 1->2 2->n5 3 3 2->3 3->n4 4 4 3->4 4->n2 5 5 4->5 5->n3 6 6 5->6

實作

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        cr = root
        while cr:
            if cr.left:
                left_tail = cr.left
                while left_tail.right:
                    left_tail = left_tail.right
                left_tail.right = cr.right
                cr.right = cr.left
                cr.left = None
            cr = cr.right

時間複雜度

這個做法由於每個節點會成為一次cr，將cr的右側的子樹合併至左側的時間複雜度為$O(1)$，圖中有n個節點，時間複雜度為$O(n)$