105. Construct Binary Tree from Preorder and Inorder Traversal

Problem link

Thoughts

preorder的組成： root L R
inorder的組成： L root R

最開始的第一個關鍵，是要想到用preorder作為建構順序，
並利用inorder判斷child應該要接在left or right subtree。

第二個關鍵，是要想到該如何「判斷」child該些在left or right subtree
舉一個小例子，preorder 順序為 [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。

到目前為止，已經可以寫出一個可行解了
用recursive function實作 preorder 建構順序，
並用二、三關鍵來實作function內容。

Time complexity: O(n)
Space complexity: O(n)

優化

考量到input的組成特性：
preorder的組成： root L R
inorder的組成： L root R

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

這提示著：
利用 preorder 順序建構，且正要開始處理左半邊時，
可以將目前的 root 放進下一層 recursion，
當 inorder 碰到 root 代表 L 已經處理完了，已經完成這一層recursion的任務了。

Implementation

# 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)