Construct Binary Tree from Preorder and Inorder Traversal

Bài toán

Cho hai mảng số nguyên preorder và inorder biểu diễn thứ tự duyệt của một cây. Hãy dựng lại cây đó.

• Preorder: Root -> Left -> Right. (Phần tử đầu tiên LUÔN là Root).
• Inorder: Left -> Root -> Right. (Root chia đôi mảng thành con trái và con phải).

Ví dụ:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Phân Tích & Tiếp Cận

Logic Chia để Trị

1. Tìm Root: preorder[0] chính là Root (số 3).
2. Chia nhánh: Tìm vị trí của số 3 trong mảng inorder. (Tại index 1).
   • Phần bên trái số 3 trong inorder ([9]) chính là Cây con trái.
   • Phần bên phải số 3 trong inorder ([15, 20, 7]) chính là Cây con phải.
3. Đệ quy: Lặp lại quy trình cho 2 mảng con.

Lưu ý: Ta cần cắt mảng preorder tương ứng với số lượng phần tử của nhánh trái và nhánh phải.

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (!preorder.length || !inorder.length) {
        return null;
    }

    // 1. Root luôn là đầu tiên của Preorder
    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);

    // 2. Tìm vị trí cắt trong Inorder
    const mid = inorder.indexOf(rootVal);

    // 3. Đệ quy
    // Inorder trái: từ 0 đến mid
    // Preorder trái: từ 1 đến mid + 1 (bỏ root đầu tiên đi)
    root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
    
    // Inorder phải: từ mid + 1 đến hết
    // Preorder phải: từ mid + 1 đến hết
    root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));

    return root;
}

Tối ưu hóa (Space)

Việc dùng slice tạo ra rất nhiều bản sao mảng ($O(n^2)$ space). Ta có thể tối ưu bằng cách truyền chỉ số (left, right) thay vì cắt mảng. Và dùng Hash Map để tra cứu vị trí trong inorder nhanh hơn ($O(1)$ thay vì indexOf $O(n)$).

• Time Complexity: $O(n^2)$ cho bản slice. $O(n)$ cho bản tối ưu Index.
• Space Complexity: $O(n^2)$ hoặc $O(n)$.

Pattern Nhận Diện

Bài toán tái tạo cấu trúc (Reconstruction) dựa trên các ràng buộc logic. Mấu chốt là xác định: Đâu là gốc? Đâu là ranh giới trái/phải?