Construct Binary Tree from Preorder and Inorder Traversal

LC 105 題意

• 已知二元樹的前序遍歷（Preorder）與中序遍歷（Inorder）結果，構建該二元樹。
• Example
  Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  Output: [3,9,20,null,null,15,7]

thoughts

• 前序的第一個節點 → 根節點。
• 在中序中找到該根節點的位置：
  • 左半部 → 左子樹
  • 右半部 → 右子樹
• 遞迴構建。
  為避免反覆尋找索引，用 HashMap 儲存 inorder 中值的位置。

Kotlin

class Solution {
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        val map = inorder.withIndex().associate { it.value to it.index }
        var preIndex = 0

        fun helper(left: Int, right: Int): TreeNode? {
            if (left > right) return null
            val rootVal = preorder[preIndex++]
            val root = TreeNode(rootVal)
            val mid = map[rootVal]!!
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        }

        return helper(0, inorder.lastIndex)
    }
}

Follow-up

• 若只有一個遍歷結果能否構建？
  • → 不行，需至少兩種（前序 + 中序 或 中序 + 後序）。
• 若節點值重複如何處理？
  • → 需改用節點索引或唯一 ID。
• 若輸入非常大（>10^5），如何避免遞迴？
  • → 改用 Stack 模擬建樹過程。