Tái tạo binary tree từ hai dấu vân tay traversal

Preorder và inorder cùng nhau xác định duy nhất một binary tree — với điều kiện tất cả giá trị node là phân biệt. Trực giác rất gọn: preorder thăm root trước children, nên preorder[0] luôn là root của subtree hiện tại. Inorder thăm left subtree rồi mới đến root rồi mới đến right subtree, nên khi biết giá trị root, bạn tìm vị trí của nó trong inorder — tất cả bên trái tạo thành left subtree, tất cả bên phải tạo thành right subtree. Sự phân chia đó cho biết kích thước của hai subtree, từ đó suy ra chính xác vị trí của các đoạn preorder tương ứng. Recursion lúc này là hoàn toàn.

Sơ đồ trên trace ví dụ đầu tiên: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. Node 3 là root; index của nó trong inorder là 1, nên 1 node đi về trái (node 9) và 3 node đi về phải (15, 20, 7). Preorder sau đó được chia tương ứng, và recursion tiếp tục.

Đề bài

Cho hai mảng số nguyên preorder và inorder — trong đó preorder là kết quả duyệt preorder của một binary tree và inorder là kết quả duyệt inorder của cùng cây đó — hãy tái tạo và trả về binary tree đó. Đề gốc: LeetCode 105.

Ràng buộc:
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder và inorder gồm các giá trị duy nhất.
- Mỗi giá trị của inorder cũng xuất hiện trong preorder.
- preorder được đảm bảo là kết quả duyệt preorder của cây.
- inorder được đảm bảo là kết quả duyệt inorder của cây.

Constraints nói gì

Bài toán nêu 1 <= preorder.length <= 3000 và tất cả giá trị là duy nhất. Hai sự kiện đó cùng nhau xác định không gian thiết kế.

n = 3000 đủ nhỏ để O(n²) pass — 9 triệu phép tính không có gì với phần cứng hiện đại. Vậy nên approach naive đệ quy không phải là lỗi time-limit-exceeded; nó chỉ bỏ lại hiệu năng trên bàn. Việc tối ưu xuống O(n) tốn thêm khoảng năm dòng code và là phiên bản bạn nên nắm vững.

Tất cả giá trị duy nhất là điều kiện mang tính chất nền tảng. Nếu cho phép trùng lặp, vị trí của root trong inorder sẽ mơ hồ và bài toán trở nên không giải được nếu không có thêm thông tin. Đảm bảo uniqueness chính là điều làm cho hash map approach hợp lệ: mỗi key xuất hiện đúng một lần.

Constraint -3000 <= preorder[i], inorder[i] <= 3000 nghĩa là giá trị vừa gọn trong int. Không có lo ngại overflow ở bất kỳ đâu.

Approach 1: recursion với linear search trong inorder

Dịch trực tiếp quan sát ở trên: lấy preorder[0] làm root, gọi inorder.index(root_val) để tìm điểm chia, slice cả hai mảng, recurse.

from typing import List, Optional
 
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]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
 
        root_val = preorder[0]
        root = TreeNode(root_val)
 
        root_index = inorder.index(root_val)
 
        left_inorder = inorder[:root_index]
        right_inorder = inorder[root_index + 1:]
 
        left_preorder = preorder[1:1 + len(left_inorder)]
        right_preorder = preorder[1 + len(left_inorder):]
 
        root.left = self.buildTree(left_preorder, left_inorder)
        root.right = self.buildTree(right_preorder, right_inorder)
 
        return root

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if (preorder.Length == 0 || inorder.Length == 0) return null;
 
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);
 
        int rootIndex = Array.IndexOf(inorder, rootVal);
 
        int[] leftInorder = new int[rootIndex];
        int[] rightInorder = new int[inorder.Length - rootIndex - 1];
        Array.Copy(inorder, 0, leftInorder, 0, rootIndex);
        Array.Copy(inorder, rootIndex + 1, rightInorder, 0, rightInorder.Length);
 
        int[] leftPreorder = new int[leftInorder.Length];
        int[] rightPreorder = new int[rightInorder.Length];
        Array.Copy(preorder, 1, leftPreorder, 0, leftInorder.Length);
        Array.Copy(preorder, 1 + leftInorder.Length, rightPreorder, 0, rightInorder.Length);
 
        root.left = BuildTree(leftPreorder, leftInorder);
        root.right = BuildTree(rightPreorder, rightInorder);
 
        return root;
    }
}

Time: O(n²). Ở mỗi level của recursion, lệnh gọi inorder.index (Python) hay Array.IndexOf (C#) quét tới n phần tử. Trong trường hợp xấu nhất — cây lệch hoàn toàn về phải — recursion thực hiện n lần gọi, mỗi lần quét danh sách ngắn dần: n + (n-1) + ... + 1 = O(n²). Space cũng là O(n²) vì array slicing tạo bản sao ở mỗi lần gọi.

Với n = 3000 điều này ổn. Với n = 100,000 thì không.

Approach 2: hash map + theo dõi index (O(n))

Hai quan sát cắt giảm chi phí:

1. Xây dựng hash map {value: inorder_index} một lần ngay từ đầu biến mỗi lần tra cứu root từ O(n) xuống O(1).
2. Thay vì slice mảng, truyền các boundary index (left, right) vào hàm đệ quy lồng nhau. Preorder index tiến toàn cục theo mỗi root được tiêu thụ.

from typing import List, Optional
 
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        self.preorder_idx = 0
 
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
 
            root_val = preorder[self.preorder_idx]
            self.preorder_idx += 1
 
            root = TreeNode(root_val)
            root_pos = inorder_map[root_val]
 
            # Left subtree phải được xây TRƯỚC right subtree
            # vì preorder_idx tiến theo thứ tự preorder (root-left-right)
            root.left = build(left, root_pos - 1)
            root.right = build(root_pos + 1, right)
 
            return root
 
        return build(0, len(inorder) - 1)

public class Solution {
    private Dictionary<int, int> inorderMap;
    private int preorderIdx;
 
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        inorderMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++)
            inorderMap[inorder[i]] = i;
 
        preorderIdx = 0;
        return Build(preorder, 0, inorder.Length - 1);
    }
 
    private TreeNode Build(int[] preorder, int left, int right) {
        if (left > right) return null;
 
        int rootVal = preorder[preorderIdx++];
        TreeNode root = new TreeNode(rootVal);
 
        int rootPos = inorderMap[rootVal];
 
        // Left trước right — preorder_idx phải đồng bộ với thứ tự duyệt preorder
        root.left = Build(preorder, left, rootPos - 1);
        root.right = Build(preorder, rootPos + 1, right);
 
        return root;
    }
}

Time: O(n). Mỗi node được thăm đúng một lần; mỗi lần tra cứu trong inorder_map là O(1). Space: O(n) cho hash map cộng với O(n) độ sâu call stack tối đa (cây lệch). Call stack của cây cân bằng là O(log n).

Tại sao left trước right không phải tùy chọn

preorder_idx là một bộ đếm toàn cục theo dõi phần tử nào trong preorder chúng ta tiêu thụ tiếp theo. Preorder thăm root, sau đó toàn bộ left subtree, sau đó toàn bộ right subtree. Nếu bạn gọi build(root_pos + 1, right) (right subtree) trước build(left, root_pos - 1) (left subtree), bộ đếm sẽ tiêu thụ các phần tử của đoạn right subtree trong khi left subtree đang chờ chúng, và bạn sẽ xây dựng sai cây. Thứ tự của hai lời gọi đệ quy này mang ý nghĩa ngữ nghĩa, không chỉ là phong cách code.

Trace tay: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

inorder_map = {9:0, 3:1, 15:2, 20:3, 7:4}
preorder_idx = 0

build(left=0, right=4):
  root_val = preorder[0] = 3, preorder_idx -> 1
  root_pos = inorder_map[3] = 1
  root.left = build(left=0, right=0)      <- left subtree của 3
  root.right = build(left=2, right=4)     <- right subtree của 3

  build(left=0, right=0):
    root_val = preorder[1] = 9, preorder_idx -> 2
    root_pos = inorder_map[9] = 0
    root.left = build(left=0, right=-1) -> None
    root.right = build(left=1, right=0) -> None  [left > right]
    return TreeNode(9)

  build(left=2, right=4):
    root_val = preorder[2] = 20, preorder_idx -> 3
    root_pos = inorder_map[20] = 3
    root.left = build(left=2, right=2)   <- left subtree của 20
    root.right = build(left=4, right=4)  <- right subtree của 20

    build(left=2, right=2):
      root_val = preorder[3] = 15, preorder_idx -> 4
      root_pos = inorder_map[15] = 2
      root.left = build(left=2, right=1) -> None
      root.right = build(left=3, right=2) -> None
      return TreeNode(15)

    build(left=4, right=4):
      root_val = preorder[4] = 7, preorder_idx -> 5
      root_pos = inorder_map[7] = 4
      root.left = build(left=4, right=3) -> None
      root.right = build(left=5, right=4) -> None
      return TreeNode(7)

    return TreeNode(20, left=15, right=7)

return TreeNode(3, left=9, right=TreeNode(20, left=15, right=7))

Cây kết quả khớp với output mong đợi [3,9,20,null,null,15,7].

Các edge case thực sự quan trọng

Cây chỉ có một node (preorder = [-1], inorder = [-1]): build(0, 0) chạy một lần, tiêu thụ preorder[0], tìm root_pos = 0, rồi gọi build(0, -1) và build(1, 0) — cả hai có left > right và trả về None. Trả về TreeNode(-1). Đúng.

Cây lệch hoàn toàn về trái (preorder = [1,2,3], inorder = [3,2,1]): Root của mỗi subtree không có right child. Recursion đi sâu n level, mỗi lần chia thành left subtree kích thước n-1 và right subtree kích thước 0. Call stack đạt độ sâu n. Với n = 3000, đó là 3000 stack frame — vượt giới hạn mặc định 1000 của Python, cần điều chỉnh sys.setrecursionlimit. C# có default stack depth lớn hơn nhiều, không vấn đề gì.

Cây lệch hoàn toàn về phải (preorder = [1,2,3], inorder = [1,2,3]): Đối xứng với trường hợp trên. Cùng vấn đề về độ sâu. Trong trường hợp này, mỗi lần gọi tạo ra node không có left child; right subtree luôn là toàn bộ phần còn lại.

Tất cả giá trị âm (ví dụ preorder = [-3,-9,-20]): hash map key là số nguyên âm, cả Python lẫn C# đều xử lý bình thường. Thuật toán không thay đổi.

Giá trị tại biên constraint (preorder[i] = -3000 hoặc 3000): không có gì đặc biệt. Giá trị vừa trong int, hash map lookup là O(1) bất kể giá trị.

Lưu ý rằng bài toán loại trừ explicitly các giá trị trùng lặp — tất cả giá trị là duy nhất. Nếu có trùng lặp, cả hai approach đều sẽ hỏng theo cùng một cách: inorder.index trả về lần xuất hiện đầu tiên, hash map sẽ ghi đè các entry trước. Bài toán đó (LeetCode 889) cần approach khác.

Bảng so sánh

Nên viết phiên bản nào

Tôi chọn phiên bản hash map mọi lúc. Logic về cơ bản giống hệt approach naive — cùng cấu trúc recursion, cùng ý tưởng chia đôi — nhưng xây dựng hash map một lần và truyền index thay vì slice mảng thì gọn gàng hơn để suy luận và scale tốt hơn với input lớn mà không cần điều chỉnh. Chi phí về nhận thức từ biến thêm (self.preorder_idx trong Python, instance variable trong C#) là nhỏ so với lợi ích thuật toán thực sự.

Phiên bản naive đáng hiểu vì nó thể hiện ý tưởng cốt lõi một cách rõ nhất: literally slice mảng, đưa slice vào recursion, tin tưởng vào base case. Nếu bạn giải thích thuật toán cho ai đó lần đầu, hãy bắt đầu ở đó. Nếu bạn đang viết solution, viết phiên bản hash map.

Ràng buộc thứ tự preorder_idx — left subtree trước right — là chi tiết duy nhất hay làm người ta vấp. Hãy đặt nó làm comment trong code.

Vị trí trong series trees

Đây là bài construction đầu tiên trong series. Tới thời điểm này (Same Tree, Subtree of Another Tree, Balanced Binary Tree và những bài khác), các bài đều yêu cầu bạn đọc một cây và trả về giá trị hay boolean. Ở đây bạn đang xây dựng cây từ đầu. Recursion có cùng hình dạng divide-and-conquer, nhưng kiểu trả về thay đổi từ scalar sang node, và các lời gọi đệ quy gán children thay vì rút gọn một phép so sánh.

Pattern nền tảng đáng đặt tên: divide-and-conquer trên các subsequence traversal. Bạn có một chuỗi mà một thứ tự traversal cho phép bạn xác định root, và chuỗi kia cho phép bạn phân vùng. Cấu trúc đó xuất hiện trong nhiều bài gần đây.

LeetCode 106 — Construct Binary Tree from Inorder and Postorder Traversal là sibling trực tiếp: inorder vẫn cho bạn điểm chia, nhưng giờ postorder cho bạn root (phần tử cuối, không phải đầu). Kỹ thuật hash map chuyển giao trực tiếp; chỉ thay đổi logic index.

LeetCode 889 — Construct Binary Tree from Preorder and Postorder Traversal khó hơn vì thiếu inorder. Root của left subtree là preorder[1], và bạn dùng vị trí của nó trong postorder để tìm kích thước left subtree. Chỉ hoạt động với full binary tree (mỗi node có 0 hoặc 2 children), đó là lý do bài toán đảm bảo điều đó.

LeetCode 297 — Serialize and Deserialize Binary Tree đảo ngược chiều: mã hóa cây thành string, rồi tái tạo lại. Giải mã chính xác là cùng loại logic "lấy token tiếp theo, recurse" như kỹ thuật preorder_idx ở đây.

LeetCode 1008 — Construct Binary Search Tree from Preorder Traversal giới hạn ở BST: bạn biết mọi thứ nhỏ hơn root đi về trái, mọi thứ lớn hơn đi về phải. Không cần mảng inorder; tính chất BST tự làm việc phân chia. So sánh với bài 105, nơi uniqueness và mảng inorder làm cùng việc đó cho cây tổng quát.