Lowest Common Ancestor of a Binary Tree

Q: Điều này khác gì so với tổ tiên chung thấp nhất trong cây tìm kiếm nhị phân?

Trong cây tìm kiếm, so sánh p và q với một nút sẽ cho bạn biết mỗi giá trị nằm ở phía nào, nhờ đó chỉ cần đi theo một đường từ gốc là tìm được đáp án trong O(h). Ở đây, phép so sánh không cho biết gì, nên bạn tìm kiếm trong các cây con.

Q: Bạn có thể tìm tổ tiên chung gần nhất bằng các con trỏ đến nút cha không?

Có. Trong mảng này, nút cha của chỉ số i là (i-1)/2 sau khi làm tròn xuống. Đưa chỉ số lớn hơn trong hai chỉ số lên nút cha của nó cho đến khi chúng bằng nhau; chỉ số lớn hơn không bao giờ là tổ tiên của chỉ số nhỏ hơn. Với các nút liên kết, thêm các tổ tiên của p vào một tập hợp rồi đi lên từ q đến nút đầu tiên có trong tập hợp đó.

Trung bìnhDuyệt cây Đệ quy

+10

Bạn nhận được một cây nhị phân trong mảng root, được sắp xếp theo thứ tự heap: nút gốc ở chỉ số 0, các nút con của chỉ số i ở 2*i+1 (bên trái) và 2*i+2 (bên phải), còn vị trí trống được biểu thị bằng -1. Các giá trị khác nhau và không theo thứ tự nào.

Trả về giá trị của tổ tiên chung thấp nhất của p và q, là giá trị của hai nút khác nhau: nút sâu nhất có cây con chứa cả hai. Cây con bao gồm nút trên cùng, vì vậy nếu q nằm bên dưới p, đáp án là p.

Hàm

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

rootinteger-array: cây nhị phân theo thứ tự từng mức, với -1 cho vị trí trống
pinteger: giá trị của một nút
qinteger: giá trị của một nút khác
Trả vềinteger: giá trị của nút thấp nhất có cây con chứa cả p và q

Ràng buộc

2 ≤ root.length ≤ 32767
Mỗi root[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ root[i] ≤ 10⁴.
root[0] không bao giờ là -1, và cây có ít nhất hai 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 một vị trí trống cũng đều trống, và độ sâu tối đa là 14.
Tất cả giá trị trong cây đều khác nhau và không theo thứ tự nào.
p và q là giá trị của hai nút khác nhau trong cây, theo thứ tự bất kỳ.

Ví dụ

Đầu vào: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Đầu ra: 3
Giải thích: 6 là nút con bên trái của 3, còn 9 nằm bên dưới 4, ở bên phải 3, nên chúng gặp nhau tại 3. Nếu so sánh các giá trị, bạn sẽ hướng đến nút gốc 8: 6 nhỏ hơn và 9 lớn hơn.

Đầu vào: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Đầu ra: 4
Giải thích: 7 là nút con bên trái của 4, và cây con của 4 bao gồm chính 4, nên đáp án là 4.

Đầu vào: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Đầu ra: 6
Giải thích: Nút gốc 1 không có nút con bên trái. Nút con bên phải 6 có 3 ở bên trái và 0 ở bên phải, nên các giá trị gặp nhau tại 6.

Câu hỏi mở rộng

Nếu p hoặc q có thể không xuất hiện, với -1 là đáp án, cách viết tắt nào trong lượt duyệt duy nhất sẽ không còn đúng, và bạn vẫn hoàn thành trong một lượt duyệt như thế nào?

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

Không có thứ tự nào cho bạn biết phía nào chứa giá trị, nên bạn phải tự kiểm tra. Một lượt duyệt hậu thứ tự cho phép mỗi cây con báo lại những gì nó tìm thấy, và các giá trị gặp nhau tại nút đầu tiên nhận được thông tin từ cả hai phía.

Đi xuống, tìm kiếm ở mỗi bên

Ý tưởng

Đi xuống từ nút gốc, tại mỗi nút hãy tìm p và q trong cây con bên trái. Nếu cả hai đều ở đó, đi sang trái. Nếu không có giá trị nào ở đó, đi sang phải. Nếu mỗi giá trị ở một bên, các giá trị nằm ở hai nhánh khác nhau, và nút này chính là đáp án. Nút chứa p hoặc q cũng là đáp án, vì giá trị còn lại phải nằm bên dưới nó. Với 6 và 9, nút gốc tìm thấy cả hai ở bên trái, còn tại 3, nút chỉ chứa 6 có mỗi p.

Mỗi bước đi xuống đều tìm kiếm cả một cây con, nên h cấp tốn O(n·h), và tốn O(n²) trên cây cao, hẹp không giới hạn độ sâu. Lần tìm kiếm tại 8 đã duyệt mọi nút bên dưới 3, và bước tại 3 duyệt lại một số nút.

Thuật toán

Viết contains(i, value): trả về false nếu vị trí trống (vượt quá cuối hoặc là -1), true nếu root[i] bằng value, nếu không thì kiểm tra cả hai nút con.
Bắt đầu tại i = 0. Nếu root[i] là p hoặc q, hãy trả về giá trị đó.
Nếu cây con bên trái tại 2*i+1 chứa cả hai giá trị, chuyển đến đó. Nếu cây con đó không chứa giá trị nào, chuyển đến 2*i+2.
Nếu không, hãy trả về root[i].

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

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Một lượt duyệt hậu tự

Ý tưởng

Để mỗi cây con trả lời một lần, từ dưới lên. find(i) trả về chỉ số của nút chứa đáp án nếu cây con tại i chứa cả hai giá trị, chỉ số của p hoặc q nếu cây con chỉ chứa một giá trị, và -1 nếu không chứa giá trị nào.

Nút chứa p hoặc q trả về chỉ số của chính nó mà không cần xem các nút bên dưới. Nếu giá trị còn lại nằm trong cây con của nó, nút này là đáp án; nếu không, một nút ở phía trên sẽ nhận được kết quả từ cả hai phía. Mọi nút khác hỏi cả hai nút con. Hai kết quả có nghĩa là hai giá trị đến từ hai phía khác nhau và gặp nhau tại đây. Một kết quả duy nhất được chuyển lên trên không đổi, dù đó là một giá trị hay đáp án đã hoàn chỉnh.

Trong ví dụ đầu tiên, 3 nhận chỉ số 3 từ bên trái và 10 từ bên phải, trả về chỉ số của chính nó là 1, rồi nút gốc chuyển kết quả lên trên. Mỗi nút chỉ được duyệt một lần: thời gian O(n), đệ quy O(h).

Thuật toán

find(i) trả về -1 nếu chỉ số vượt quá cuối mảng hoặc có giá trị là -1.
Nút có giá trị là p hoặc q trả về i mà không tìm xuống các nút bên dưới.
Mọi nút khác tính left = find(2*i+1) và right = find(2*i+2). Nếu cả hai đều không phải -1, nút trả về i; nếu không, trả về giá trị không phải -1, hoặc -1.
Trả về root[find(0)].

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

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

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

So sánh giá trị với nút. Cây không có thứ tự: trong ví dụ đầu tiên, quá trình duyệt dừng ở nút gốc 8 thay vì 3.
Truyền lên true hoặc false thay vì một chỉ số. Nút cha không thể biết liệu đáp án đã tìm được có nằm bên dưới nó hay chưa.
Đọc nút con mà không kiểm tra độ dài. Nút 9 ở chỉ số 10 có các chỉ số nút con là 21 và 22, nằm ngoài phần tử cuối cùng.
Trả về find(0), tức một chỉ số, thay vì root[find(0)].
Trong Lua và R, mảng bắt đầu từ 1: hãy giữ chỉ số nút bắt đầu từ 0 và đọc root[i + 1].

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

Độ phức tạp thời gian của thuật toán tìm tổ tiên chung thấp nhất trong cây nhị phân là bao nhiêu?

Lượt duyệt hậu tự đi vào mỗi nút nhiều nhất một lần: thời gian O(n). Ngăn xếp đệ quy giữ một khung cho mỗi cấp, nên độ phức tạp không gian là O(log n) trên cây cân bằng và O(n) trên cây có dạng đường đi.

Điều này khác gì so với tổ tiên chung thấp nhất trong cây tìm kiếm nhị phân?

Trong cây tìm kiếm, so sánh p và q với một nút sẽ cho bạn biết mỗi giá trị nằm ở phía nào, nhờ đó chỉ cần đi theo một đường từ gốc là tìm được đáp án trong O(h). Ở đây, phép so sánh không cho biết gì, nên bạn tìm kiếm trong các cây con.

Bạn có thể tìm tổ tiên chung gần nhất bằng các con trỏ đến nút cha không?

Có. Trong mảng này, nút cha của chỉ số i là (i-1)/2 sau khi làm tròn xuống. Đưa chỉ số lớn hơn trong hai chỉ số lên nút cha của nó cho đến khi chúng bằng nhau; chỉ số lớn hơn không bao giờ là tổ tiên của chỉ số nhỏ hơn. Với các nút liên kết, thêm các tổ tiên của p vào một tập hợp rồi đi lên từ q đến nút đầu tiên có trong tập hợp đó.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Đầu ra mong đợi