Tái Xây Dựng Cây Nhị Phân (Tree Reconstruction)

Từ kết quả Preorder và Inorder để ráp nối lại cấu trúc rễ - mầm nguyên bản.

Preorder (Gốc - Trái - Phải)

3
9
20
15
7

Inorder (Trái - Gốc - Phải)

9
3
15
20
7
Khởi tạo đệ quy với toàn bộ 2 mảng Preorder và Inorder.
Tốc Độ

🧠 Định Lý Divide & Conquer

Làm thế nào để phục dựng nguyên bản 1 cây khi nó đã bị là phẳng thành mảng 1D? Ta cần 2 manh mối (2 mảng).

Preorder (G-T-P): Luôn cung cấp 1 sự thật: Phần tử đầu tiên của bất kỳ đoạn cắt nào CŨNG LÀ GỐC (Root).
Inorder (T-G-P): Sau khi biết Gốc từ Preorder, dò nó trên Inorder. Gốc sẽ phân chia ranh giới: bên Trái là mầm bên trái, bên Phải là mầm bên phải.

Đệ quy liên tục đập vỡ, lấy gốc, tìm vùng, đập vỡ... cho tới khi mảng trống.