Construct Binary Tree from Preorder and Inorder Traversal

Q: Bạn có thể dựng lại cây nhị phân từ thứ tự trước và thứ tự sau không?

Không phải lúc nào cũng vậy. Duyệt trước [1, 2] và duyệt sau [2, 1] đều phù hợp với cả cây con trái lẫn cây con phải, vì không cách duyệt nào đặt nút gốc ở giữa các cây con. Cặp này chỉ đủ để xác định một cây nhị phân đầy đủ, trong đó mỗi nút có không hoặc hai cây con.

Trung bìnhDuyệt cây Băm Đệ quy

+10

Bạn nhận được hai mảng, preorder và inorder, liệt kê các giá trị phân biệt của cùng một cây nhị phân. Duyệt theo thứ tự trước sẽ thăm một nút, rồi đến cây con bên trái, sau đó đến cây con bên phải. Duyệt theo thứ tự giữa sẽ thăm cây con bên trái, rồi đến nút, sau đó đến cây con bên phải.

Hãy dựng lại cây và trả về dưới dạng mảng theo thứ tự từng tầng: nút gốc ở chỉ số 0, các nút con của chỉ số i ở 2i+1 (bên trái) và 2i+2 (bên phải), đồng thời điền -1 vào mọi vị trí trống. Mảng kết thúc ở nút cuối cùng, không có -1 ở cuối.

Hàm

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: các giá trị theo thứ tự tiền thứ tự (preorder): nút, cây con trái, cây con phải
inorderinteger-array: các giá trị theo thứ tự duyệt giữa (inorder): cây con trái, nút, cây con phải
Trả vềinteger-array: cây theo thứ tự từng mức, dùng -1 cho các vị trí trống và không có -1 ở cuối

Ràng buộc

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, và tất cả các giá trị đều khác nhau.
inorder chứa cùng các giá trị và cả hai mảng đều mô tả cùng một cây nhị phân.
Độ sâu của cây tối đa là 14, vì vậy mọi chỉ số trong đáp án đều nhỏ hơn 2¹⁴-1 = 16383.

Ví dụ

Đầu vào: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Đầu ra: [7, 3, 4, 0, 9, -1, 6]
Giải thích: Thứ tự duyệt tiền thứ tự bắt đầu từ nút gốc, 7. Nút này nằm ở vị trí 3 trong thứ tự duyệt trung thứ tự, nên 0, 3, 9 nằm bên trái và 4, 6 nằm bên phải. 4 chỉ có nút con bên phải là 6, nên chỉ số 5 giữ nguyên giá trị -1.

Đầu vào: preorder = [1, 2, 3]inorder = [2, 3, 1]
Đầu ra: [1, 2, -1, -1, 3]
Giải thích: Nút gốc 1 nằm cuối trong inorder, nên chỉ số 2 là -1. Trong hai nút 2, 3, thứ tự trước (preorder) liệt kê 2 trước, còn thứ tự giữa (inorder) đặt 3 sau nó, nên 3 là nút con bên phải của nó, tại chỉ số 4.

Câu hỏi mở rộng

Bạn có thể dựng lại cây mà không dùng đệ quy, chỉ duyệt preorder một lượt với một ngăn xếp tường minh không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Duyệt trước (preorder) cho biết nút gốc của mỗi cây con: giá trị đầu tiên trong đoạn tương ứng. Duyệt giữa (inorder) cho biết vị trí phân chia: các giá trị trước nút gốc nằm bên trái, các giá trị sau nó nằm bên phải. Gọi đệ quy trên cả hai nửa sẽ dựng lại cây, còn ánh xạ từ giá trị sang vị trí trong thứ tự duyệt giữa giúp tra cứu mỗi nút gốc chỉ bằng một bước.

Chia đệ quy, quét tìm nút gốc

Ý tưởng

Trong preorder, cây con trái theo sau nút gốc và chiếm một mục cho mỗi giá trị, tức m-lo mục, trong đó m là vị trí của nút gốc trong inorder. Cây con phải nằm sau nó, nên nút gốc của cây con phải ở vị trí pre+1+(m-lo). Trong ví dụ đầu tiên, phần bên trái 0, 3, 9 có ba giá trị, vì vậy cây con phải bắt đầu tại chỉ số preorder 4, với giá trị 4.

Độ sâu tối đa 14 giữ mọi chỉ số đầu ra dưới 2^14-1. Điền -1 vào bấy nhiêu ô, ghi mỗi giá trị tại chỉ số tương ứng, rồi cắt bỏ các mục -1 ở cuối.

Quét từng khoảng inorder để tìm nút gốc tốn O(n·h): các khoảng ở cùng một mức không chồng lấp, nên mỗi mức quét tối đa n mục, ở đây tối đa 14 × 3000 = 42000 bước. Nếu không giới hạn độ sâu, cây có hình dạng như một đường đi sẽ khiến độ phức tạp là O(n²).

Thuật toán

Tạo out với 2^14-1 phần tử, tất cả đều là -1.
Viết build(pre, lo, hi, h): nếu lo > hi, hãy trả về. Nếu không, ghi preorder[pre] vào out[h].
Duyệt inorder từ lo để tìm vị trí m của nút gốc. Cây con bên trái có m-lo giá trị.
Gọi build(pre+1, lo, m-1, 2*h+1) và build(pre+1+(m-lo), m+1, hi, 2*h+2).
Gọi build(0, 0, n-1, 0), sau đó bỏ các phần tử -1 ở cuối và trả về phần còn lại.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Tách đệ quy bằng bản đồ vị trí

Ý tưởng

Các giá trị không trùng nhau, nên mỗi giá trị chỉ có đúng một vị trí trong inorder. Hãy ghi vị trí đó vào một bản đồ ánh xạ từ giá trị sang vị trí trước khi đệ quy bắt đầu, khi đó mỗi lần tra cứu nút gốc chỉ mất một bước.

Việc tạo bản đồ mất O(n), sau đó mỗi giá trị được đặt vào đúng một lần với lượng công việc không đổi, nên tổng thời gian là O(n). Bản đồ cần O(n) dung lượng và mỗi cấp đệ quy cần một khung. Trong C và R, các giá trị không vượt quá 10^4, nên một mảng thông thường gồm 10^4+1 phần tử có thể dùng làm bản đồ.

Thuật toán

Tạo một ánh xạ từ mỗi giá trị của inorder đến vị trí của nó.
Tạo out với 2^14-1 phần tử, tất cả đều là -1.
Trong build(pre, lo, hi, h), trả về nếu lo > hi; nếu không, ghi preorder[pre] vào out[h] rồi tra vị trí m của nó trong ánh xạ.
Gọi đệ quy với build(pre+1, lo, m-1, 2*h+1) và build(pre+1+(m-lo), m+1, hi, 2*h+2).
Gọi build(0, 0, n-1, 0), rồi loại bỏ các phần tử -1 ở cuối và trả về phần còn lại.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Lỗi thường gặp và trường hợp biên

Bắt đầu cây con bên phải (right subtree) tại pre+1+m thay vì pre+1+(m-lo). Cách này hoạt động khi lo là 0, như ở lời gọi đầu tiên, nhưng sẽ sai khi một phạm vi (range) bắt đầu muộn hơn.
Bỏ qua các khoảng trống. Một nút con bị thiếu vẫn chiếm vị trí, vì vậy ví dụ thứ hai cho kết quả [1, 2, -1, -1, 3], không phải [1, 2, 3].
Để lại các phần tử -1 ở cuối. Trả về đủ 2^14-1 ô sẽ khiến ví dụ đầu tiên có thêm 16376 phần tử -1.
Sao chép các lát cắt của cả hai mảng ở mỗi lần gọi, làm tăng độ phức tạp thêm O(n) cho mỗi cấp. Hãy truyền các phạm vi chỉ số.
Trong Lua và R, mảng bắt đầu từ 1. Hãy giữ vị trí bắt đầu từ 0 để tính toán và đọc preorder[pre + 1] và out[h + 1].

Câu hỏi thường gặp3

Tại sao bạn cần cả thứ tự duyệt trước và thứ tự duyệt giữa để dựng lại cây nhị phân?

Duyệt trước không thể tự xác định cấu trúc cây. Dãy duyệt trước [1, 2] phù hợp với cây có 2 là nút con bên trái của 1 và cũng phù hợp với cây có nó là nút con bên phải. Duyệt giữa sẽ xác định điều đó: [2, 1] đặt 2 ở bên trái, còn [1, 2] đặt 2 ở bên phải. Khi các giá trị khác nhau, cặp dãy này mô tả chính xác một cây.

Độ phức tạp thời gian của việc xây dựng cây nhị phân từ thứ tự trước và thứ tự giữa là bao nhiêu?

Khi có ánh xạ từ giá trị sang vị trí trong thứ tự giữa, độ phức tạp thời gian là O(n) và cần thêm O(n) bộ nhớ. Nếu không có ánh xạ, việc quét từng phạm vi thứ tự giữa để tìm nút gốc sẽ tốn O(n·h), trở thành O(n²) với cây có hình dạng như một đường đi.

Bạn có thể dựng lại cây nhị phân từ thứ tự trước và thứ tự sau không?

Không phải lúc nào cũng vậy. Duyệt trước [1, 2] và duyệt sau [2, 1] đều phù hợp với cả cây con trái lẫn cây con phải, vì không cách duyệt nào đặt nút gốc ở giữa các cây con. Cặp này chỉ đủ để xác định một cây nhị phân đầy đủ, trong đó mỗi nút có không hoặc hai cây con.

def buildTree(preorder, inorder):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Đầu ra mong đợi

[7, 3, 4, 0, 9, -1, 6]