Lowest Common Ancestor of a BST

Q: Độ phức tạp thời gian (time complexity) của tổ tiên chung thấp nhất trong BST là bao nhiêu?

Đường đi từ nút gốc chỉ theo một lối, nên mất O(h) thời gian với cây có độ sâu h và dùng thêm O(1) bộ nhớ. Với cây cân bằng, độ phức tạp là O(log n); với cây có hình dạng như một đường đi duy nhất, độ phức tạp là O(n).

Q: LCA trong cây tìm kiếm nhị phân khác gì so với LCA trong cây nhị phân?

Trong cây nhị phân thông thường, một giá trị có thể nằm ở bất kỳ đâu, nên bạn có thể phải tìm kiếm mọi nút, với độ phức tạp O(n). Trong cây tìm kiếm, so sánh hai giá trị với một nút sẽ cho bạn biết mỗi giá trị nằm ở phía nào, vì vậy bạn chỉ cần đi theo một đường từ nút gốc.

Q: Một nút có thể là tổ tiên chung thấp nhất của chính nó không?

Có. Một nút được tính là tổ tiên của chính nó, nên khi p nằm phía trên q , đáp án là p ; còn khi hai giá trị bằng nhau, đáp án là giá trị đó.

Trung bìnhCây nhị phân tìm kiếm

+10

Bạn nhận được một cây tìm kiếm nhị phân được lưu theo thứ tự heap trong mảng tree: nút gốc nằm ở chỉ số 0, các nút con của chỉ số i nằm tại 2*i+1 (bên trái) và 2*i+2 (bên phải), còn -1 đánh dấu vị trí trống. Mọi giá trị trong cây con bên trái của một nút đều nhỏ hơn giá trị của nút đó, và mọi giá trị trong cây con bên phải đều lớn hơn.

Hãy viết lowestCommonAncestor, hàm trả về giá trị của tổ tiên chung thấp nhất của hai giá trị p và q, cả hai đều có trong cây: nút sâu nhất có cả hai giá trị trong cây con của nó. Một nút thuộc cây con của chính nó, vì vậy nếu p nằm phía trên q, đáp án là p.

Hàm

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: cây tìm kiếm nhị phân theo thứ tự từng mức, với -1 cho vị trí trống
pinteger: giá trị đầu tiên cần tìm
qinteger: giá trị thứ hai cần tìm
Trả vềinteger: giá trị của nút sâu nhất có cả p và q trong cây con

Ràng buộc

1 ≤ tree.length ≤ 32767
Mỗi tree[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ tree[i] ≤ 10⁵.
tree[0] không bao giờ là -1, nên cây có ít nhất một nút.
Mảng có thể kết thúc bằng các phần tử -1 thừa sau nút cuối cùng.
Cả hai nút con của vị trí trống cũng đều trống, và độ sâu tối đa là 14.
Cây là một cây tìm kiếm nhị phân hợp lệ, vì vậy tất cả các giá trị của nó đều khác nhau.
p và q là giá trị của các nút trong cây. Chúng có thể xuất hiện theo thứ tự bất kỳ và có thể bằng nhau.

Ví dụ

Đầu vào: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Đầu ra: 8
Giải thích: Khi đi lên từ 3 và 15, nút đầu tiên mà cả hai cùng gặp là 8: 3 là nút con bên trái của nó, còn 15 nằm bên dưới 12 ở nhánh phải. Nút gốc 20 cũng là tổ tiên chung, nhưng ở vị trí cao hơn.

Đầu vào: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Đầu ra: 12
Giải thích: 10 là nút con bên trái của 12, và một nút được tính là tổ tiên của chính nó, nên 12 chứa cả hai giá trị, còn các nút bên dưới nó thì không. Ở đây, p là giá trị lớn hơn.

Đầu vào: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Đầu ra: 70
Giải thích: Cả hai giá trị đều lớn hơn nút gốc 50, nên cả hai đều nằm bên phải nút này. Đến nút 70, chúng tách ra: 55 nhỏ hơn nên nằm bên trái, bên dưới 60, còn 80 lớn hơn.

Câu hỏi mở rộng

Bạn sẽ thay đổi điều gì nếu p hoặc q có thể không có trong cây và hàm phải trả về -1 trong trường hợp đó?

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

Cây tìm kiếm cho bạn biết giá trị nằm ở đâu tại mỗi nút: giá trị nhỏ hơn ở bên trái, giá trị lớn hơn ở bên phải. Bắt đầu từ nút gốc rồi đi về phía chứa cả hai giá trị. Nút đầu tiên mà hai giá trị không còn nằm cùng một phía chính là đáp án, và bạn đến đó theo một đường đi.

Tìm kiếm toàn bộ cây, không xét thứ tự

Ý tưởng

Phương thức này hoạt động với mọi cây nhị phân. Hàm đệ quy find(i) báo cho biết cây con tại i chứa gì. Một nút chứa p hoặc q sẽ báo chính nó: nếu giá trị còn lại nằm bên dưới nó thì đó là đáp án, còn nếu không, một nút ở phía trên sẽ thấy cả hai. Mọi nút khác sẽ hỏi cả hai nút con. Nếu cả hai đều báo có giá trị, p và q nằm ở hai phía khác nhau, và nút này là nơi chúng gặp nhau; nếu chỉ một nút con báo có giá trị, hãy truyền giá trị đó lên.

Với 3 và 15, nút 8 nhận chỉ số 3 từ bên trái và chỉ số 10 từ bên phải rồi báo chính nó. Phương thức này có thể duyệt mọi nút: thời gian O(n) và O(h) cho đệ quy.

Thuật toán

Viết find(i). Nếu vị trí tại i trống (nằm ngoài cuối mảng hoặc là -1), trả về -1.
Nếu tree[i] là p hoặc q, trả về i.
Gọi find với 2*i+1 và 2*i+2. Nếu cả hai đều tìm thấy kết quả, trả về i.
Nếu không, trả về kết quả tìm thấy ở một trong hai nhánh, hoặc -1.
Trả về tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

So sánh hai đường đi tìm kiếm

Ý tưởng

Tìm một giá trị theo cách thông thường: bắt đầu từ nút gốc, đi sang trái nếu giá trị đó nhỏ hơn nút hiện tại và sang phải nếu lớn hơn. Đường đi từ nút gốc đến một nút là duy nhất, nên đường đi này lần lượt qua mọi nút tổ tiên của giá trị đó và không qua nút nào khác.

Ghi lại cả hai đường đi. Chúng có các nút giống nhau cho đến khi hai giá trị đi theo hai hướng khác nhau, vì vậy phần đầu chung liệt kê các nút tổ tiên chung và giá trị cuối cùng trong phần đó là nút thấp nhất. Với 3 và 15, các đường đi là 20, 8, 3 và 20, 8, 12, 15: chúng có chung 20, 8, nên đáp án là 8. Mỗi đường đi cần một bước cho mỗi cấp: độ phức tạp thời gian O(h) và độ phức tạp bộ nhớ O(h) cho các danh sách.

Thuật toán

Viết path(target): bắt đầu từ chỉ số 0, ghi lại tree[i], dừng khi giá trị này bằng target, nếu không thì chuyển đến 2*i+1 nếu target nhỏ hơn và đến 2*i+2 nếu lớn hơn.
Tạo đường đi đến p và đường đi đến q.
Duyệt cả hai danh sách từ đầu và trả về giá trị cuối cùng xuất hiện trong cả hai.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Đi xuống cho đến khi các giá trị tách ra

Ý tưởng

Hai đường đi trùng nhau khi p và q cùng bước theo một hướng, vì vậy hãy đi theo cả hai cùng lúc. Tại một nút chứa v, nếu cả hai giá trị đều nhỏ hơn, thì cả hai đều nằm trong cây con bên trái, và mọi tổ tiên chung nằm dưới v cũng vậy: hãy đi sang trái. Nếu cả hai đều lớn hơn, hãy đi sang phải.

Nếu không, một giá trị nhỏ hơn còn giá trị kia lớn hơn, nên không có nút con nào của v chứa cả hai, hoặc một trong hai giá trị bằng v, vốn là tổ tiên của chính nó. Dù trường hợp nào, v là nút sâu nhất nằm phía trên cả hai. Trong ví dụ thứ ba, 50 nằm dưới cả hai giá trị, nên bạn đi sang phải đến 70, nơi 55 nhỏ hơn còn 80 lớn hơn. Mỗi tầng cần một cặp phép so sánh, nên độ phức tạp thời gian là O(h) và độ phức tạp bộ nhớ là O(1).

Thuật toán

Bắt đầu tại chỉ số i = 0.
Đọc v = tree[i].
Nếu p < v và q < v, chuyển đến 2*i+1 rồi lặp lại.
Nếu p > v và q > v, chuyển đến 2*i+2 rồi lặp lại.
Nếu không, trả về v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

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

Dùng ≤ và ≥ trong các điều kiện kiểm tra bước di chuyển. Với p = 12 và q = 10, quá trình di chuyển đi qua 12 đến 10, sau đó trả về 10 hoặc đi ra khỏi cây.
Giả định p < q. Trong ví dụ thứ hai, p là giá trị lớn hơn. Hãy kiểm tra cả hai giá trị với nút, hoặc đổi chỗ chúng trước.
Trả về chỉ số thay vì giá trị. Đáp án là tree[i], không phải i.
Trong Lua và R, mảng bắt đầu từ 1. Giữ chỉ số nút bắt đầu từ 0 để dùng phép tính 2*i+1 và đọc tree[i + 1].

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

Độ phức tạp thời gian (time complexity) của tổ tiên chung thấp nhất trong BST là bao nhiêu?

Đường đi từ nút gốc chỉ theo một lối, nên mất O(h) thời gian với cây có độ sâu h và dùng thêm O(1) bộ nhớ. Với cây cân bằng, độ phức tạp là O(log n); với cây có hình dạng như một đường đi duy nhất, độ phức tạp là O(n).

LCA trong cây tìm kiếm nhị phân khác gì so với LCA trong cây nhị phân?

Trong cây nhị phân thông thường, một giá trị có thể nằm ở bất kỳ đâu, nên bạn có thể phải tìm kiếm mọi nút, với độ phức tạp O(n). Trong cây tìm kiếm, so sánh hai giá trị với một nút sẽ cho bạn biết mỗi giá trị nằm ở phía nào, vì vậy bạn chỉ cần đi theo một đường từ nút gốc.

Một nút có thể là tổ tiên chung thấp nhất của chính nó không?

Có. Một nút được tính là tổ tiên của chính nó, nên khi p nằm phía trên q, đáp án là p; còn khi hai giá trị bằng nhau, đáp án là giá trị đó.

def lowestCommonAncestor(tree, p, q):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Đầu ra mong đợi

Lowest Common Ancestor of a BST

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Tìm kiếm toàn bộ cây, không xét thứ tự

So sánh hai đường đi tìm kiếm

Đi xuống cho đến khi các giá trị tách ra

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

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

Bài tập tương tự