LeetCode 105: สร้าง Binary Tree จาก Preorder กับ Inorder

โจทย์ Construct Binary Tree from Preorder and Inorder Traversal ให้ลำดับการเยี่ยมโหนดสองแบบของต้นไม้เดียวกันและรับประกันว่าค่าไม่ซ้ำ เราต้องประกอบโครงสร้างเดิมกลับมาให้ได้ครับ

WHY: ลำดับหนึ่งบอกราก อีกลำดับแบ่งซ้ายขวา

preorder วางรากของ subtree ไว้ก่อนเสมอ ส่วน inorder วางสมาชิกฝั่งซ้ายก่อนรากและฝั่งขวาหลังราก เหมือนมีใบรายการหนึ่งบอกหัวหน้ากลุ่มก่อน และอีกใบเรียงคนตามที่นั่ง เมื่อจับตำแหน่งหัวหน้าได้ เราจะแบ่งสมาชิกสองฝั่งได้

วิธีที่ 1: recursive + index map

สร้าง map จากค่าไปตำแหน่งใน inorder แล้วถือ cursor บน preorder ทุกครั้งที่สร้างโหนด ใช้ช่วงซ้าย/ขวาของ inorder จำกัด subtree

• เวลา: O(n)
• หน่วยความจำ: O(n) สำหรับ map และ call stack สูงสุด O(n) เมื่อต้นไม้เอียง
• จุดเด่น: อธิบาย invariant ง่ายและตรงกับนิยาม traversal

วิธีที่ 2: iterative stack

เริ่มจากรากตัวแรกใน preorder แล้วใช้ stack เก็บเส้นทางที่ยังรอลูกขวา หากยอด stack ยังไม่ตรงกับ inorder cursor โหนดใหม่เป็นลูกซ้าย; ถ้าตรงให้ pop จนพ้นกลุ่มที่ปิดแล้ว จากนั้นต่อเป็นลูกขวา

• เวลา: O(n)
• หน่วยความจำ: O(n)
• จุดเด่น: ไม่เสี่ยง recursion depth ในภาษาที่ stack จำกัด
• ข้อแลกเปลี่ยน: invariant อ่านยากกว่าและ debug ยากเมื่อ cursor เคลื่อนผิด

วิธีที่ 3: recursive แต่ scan inorder ทุกครั้ง

หาตำแหน่งรากด้วย linear search ในแต่ละ subtree โค้ดเริ่มต้นสั้น แต่ต้นไม้เอียงทำให้เวลา O(n²) และการ slice list เพิ่ม allocation เหมาะเพียงการอธิบายแนวคิด ไม่ใช่ค่าเริ่มต้นภายใต้ constraints ใหญ่

import unittest
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


def build_recursive(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    cursor = 0

    def build(left, right):
        nonlocal cursor
        if left > right:
            return None
        value = preorder[cursor]
        cursor += 1
        middle = positions[value]
        node = TreeNode(value)
        node.left = build(left, middle - 1)
        node.right = build(middle + 1, right)
        return node

    return build(0, len(inorder) - 1)


def build_iterative(preorder, inorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    stack = [root]
    inorder_index = 0

    for value in preorder[1:]:
        node = stack[-1]
        if node.val != inorder[inorder_index]:
            node.left = TreeNode(value)
            stack.append(node.left)
        else:
            while stack and stack[-1].val == inorder[inorder_index]:
                node = stack.pop()
                inorder_index += 1
            node.right = TreeNode(value)
            stack.append(node.right)
    return root


def shape(node):
    if node is None:
        return None
    return (node.val, shape(node.left), shape(node.right))


class BuildTreeTests(unittest.TestCase):
    def test_balanced_tree(self):
        preorder = [3, 9, 20, 15, 7]
        inorder = [9, 3, 15, 20, 7]
        expected = (3, (9, None, None), (20, (15, None, None), (7, None, None)))
        self.assertEqual(shape(build_recursive(preorder, inorder)), expected)
        self.assertEqual(shape(build_iterative(preorder, inorder)), expected)

    def test_empty_and_skewed(self):
        self.assertIsNone(build_recursive([], []))
        preorder = [1, 2, 3]
        inorder = [1, 2, 3]
        self.assertEqual(
            shape(build_iterative(preorder, inorder)),
            (1, None, (2, None, (3, None, None))),
        )


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	Recursive + map	Iterative stack	Recursive scan
input ใหญ่และสมดุล	ดีมาก	ดีมาก	ช้ากว่า
ต้นไม้เอียงมาก	เสี่ยง recursion depth	ดีที่สุด	ทั้งช้าและเสี่ยง stack
memory จำกัด	map + stack	stack	ไม่ใช้ mapแต่ slice/stack ยังมีต้นทุน
readability	ดีที่สุด	ต้องอธิบาย invariant	เข้าใจง่ายแต่ performance แย่
streaming input	ต้องมี inorder ครบ	ต้องมี traversal ครบ	ไม่เหมาะ
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่านถ้าไม่ slice แบบ destructive
ค่าซ้ำ	map เดี่ยวใช้ไม่ได้	แยกต้นไม้ไม่ชัด	ต้องมีข้อมูลเพิ่ม

Best default: recursive + index map เพราะได้ O(n) และอธิบายความสัมพันธ์ของ traversal ตรงที่สุด เปลี่ยนเป็น iterative เมื่อต้นไม้เอียงอาจชน recursion limit

Edge cases

• input ว่าง
• โหนดเดียว
• ต้นไม้เอียงซ้ายหรือขวาทั้งหมด
• ค่าไม่ซ้ำเป็นเงื่อนไขสำคัญ; ถ้าซ้ำ traversal สองชุดอาจไม่ชี้ต้นไม้เดียว
• production code ควร validate ว่าความยาวและชุดค่าเท่ากันก่อนสร้าง

Recap

• preorder ให้รากตัวถัดไป
• inorder แบ่ง subtree ซ้ายและขวา
• map ลดการหาตำแหน่งจาก O(n) เหลือ O(1) ต่อโหนด
• iterative stack เหมาะเมื่อต้นไม้ลึกมาก