105. Preorder와 Inorder Traversal로부터 이진 트리 구성하기

문제 링크

105. Construct Binary Tree from Preorder and Inorder Traversal

생각

preorder的組成: root L R
inorder的組成: L 루트 R

最開始的第一個關鍵,是要想到用선주문제작為建構順序,
並利用inorder判斷child應該要接在왼쪽 또는 오른쪽 하위 트리.

第二個關鍵, 是要想到該如何「判斷」child該些在left 또는 right 서브트리
舉一個小例子, 順序為 [A B]
若inorder順序為[B A],則B應該要接在A의 左子樹
若inorder順序為[A B],則B應該要接在A的右子樹
應該放在左、右子樹,可以透過inorder中A, B的index來判斷
當B's index > A's index時,代表B是要接在A的右子數

第三個關鍵,是要想到如何「快速比較」A, B的index
最直覺的方式是用一個index hashmap,將inorder的value對應到其index.

到目前為止,已經可以寫出一個可行解了
用재귀함수實作 선주문 建構順序,
並用二、三關鍵來實作기능내容.

시간 복잡도: O(n)
공간 복잡도: O(n)

優化

考量到input的組成特性:
preorder的組成: root L R
inorder的組成: L 루트 R

可以發現,若照著 선주문 的順序建構,
當建構完 뿌리 以及整個 L 時,
inorder 也會剛好利用完 L, root 這兩個部分的資訊.
且恰好,L, root 的最後一個 element.

這提示著:
利用 선주문 順序建構,且正要開始處理左半邊時,
可以將目前的 루트 放進下一層 재귀,
當 중위 碰到 루트 代表 L 已經處理完了,已經完成這一層recursion的任務了.

구현

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        p, i = 0, 0
        def helper(stop) -> TreeNode:
            nonlocal p, i

            if p < len(preorder) and inorder[i] != stop:
                root = TreeNode(preorder[p])
                p += 1
                root.left = helper(root.val)
                i += 1
                root.right = helper(stop)
                return root
        return helper(None)

用p代表예약주문展開進度,
用i代表inorder建構進度

도우미實作예약주문順序

建立root

向L展開

向R展開

觀察後可以發現,一開始會不斷向L展開,直到遇到最左leaf的左node (없음),i維持為0
這時stop(最左leaf的value)會等於inorder[0]
並回上一層,回到最左leaf為root입니다.
此時i才會有所增加,並開始處理R

由此可知,i概念上代表的是實際上建構完的L數量,或是理解成建構進度、收斂進度

참조

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34543/Simple-O(n)-without-map