Binary Tree Right Side View

Q: Độ phức tạp thời gian và không gian của bài toán nhìn cây nhị phân từ phía bên phải là bao nhiêu?

Độ phức tạp thời gian là O(n) với n nút, và không lời giải nào có thể bỏ qua nút, vì nút ngoài cùng bên phải của một tầng có thể nằm ở bất kỳ vị trí nào. Độ phức tạp không gian là O(w) cho hàng đợi, trong đó w là độ rộng lớn nhất của một tầng, hoặc O(h) cho cách duyệt ưu tiên bên phải trên cây có h tầng.

Trung bìnhDuyệt cây Hàng đợi

+10

Mảng (array) root chứa một cây nhị phân. Gốc nằm ở chỉ số 0, các nút con của nút ở chỉ số i nằm tại 2*i+1 (bên trái) và 2*i+2 (bên phải), -1 đánh dấu một vị trí trống, và có thể có thêm các giá trị -1 ở cuối.

Hãy nhìn cây từ phía bên phải. Ở mỗi tầng, bạn chỉ thấy đúng một nút, nút nằm xa nhất về bên phải, còn các nút khác bị che khuất. Liệt kê các giá trị đó từ tầng của gốc xuống tầng sâu nhất.

Hàm

rightSideView(root: integer-array) → integer-array

rootinteger-array: cây theo thứ tự heap, với -1 cho vị trí trống
Trả vềinteger-array: giá trị ngoài cùng bên phải của mỗi cấp, bắt đầu từ cấp cao nhất

Ràng buộc

1 ≤ root.length ≤ 32767
Mỗi root[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ root[i] ≤ 10⁴.
Các giá trị nút là khác nhau.
root[0] không bao giờ là -1, vì vậy 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 dư ra 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à cây có tối đa 14 cấp.

Ví dụ

Đầu vào: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Đầu ra: [5, 9, 1, 3]
Giải thích: Từ bên phải, bạn thấy 5, 9 và 1 (chỉ số 6). Tầng thứ tư chỉ có 3, ở chỉ số 8 bên dưới 7 trong cây con bên trái. Không có nút nào ở bên phải sâu đến mức đó, nên có thể nhìn thấy 3.

Đầu vào: root = [6, 0, -1, 8, -1, -1, -1]
Đầu ra: [6, 0, 8]
Giải thích: Cây là một chuỗi các nút con bên trái: 6, 0, 8. Mỗi tầng chứa một nút, nên bạn thấy cả ba nút, dù không nút nào là nút con bên phải.

Đầu vào: root = [42]
Đầu ra: [42]
Giải thích: Một mảng có độ dài 1: nút gốc 42 hoàn toàn không có vị trí con nào, và chế độ xem chỉ có một giá trị đó.

Câu hỏi mở rộng

Làm thế nào để lấy hình chiếu từ bên phải của một cây mà mỗi nút có thể có số lượng nút con bất kỳ, được lưu dưới dạng danh sách từ trái sang phải?

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

Bạn nhìn thấy nút ngoài cùng bên phải ở mỗi tầng, và nút đó không nhất thiết phải là nút con bên phải: giá trị cuối cùng của ví dụ 1 nằm trong cây con bên trái. Tìm kiếm theo chiều rộng sẽ gặp nút đó sau cùng trong mỗi lượt; duyệt theo chiều sâu, ưu tiên đi sang phải, sẽ gặp nút đó trước mọi nút khác ở cùng tầng.

Duyệt theo chiều rộng, nút cuối cùng ở mỗi cấp

Ý tưởng

Duyệt cây từng tầng trong mỗi lượt. Khi một lượt bắt đầu, hàng đợi chứa chính xác một tầng theo thứ tự từ trái sang phải, vì vậy chỉ số cuối cùng bạn lấy ra khỏi hàng đợi trong lượt đó tương ứng với nút ngoài cùng bên phải của tầng, và giá trị của nút được đưa vào kết quả.

Trong ví dụ 1, các lượt là [5], [2, 9], [7, 4, 1] và [3], các phần tử cuối cùng của chúng cho kết quả 5, 9, 1, 3. Tầng mới là yếu tố quyết định, không phải phía: 3 nằm ở cây con bên trái, nhưng nó là nút duy nhất ở tầng của mình.

Mỗi chỉ số được thêm vào và lấy ra khỏi hàng đợi một lần, nên thời gian chạy là O(n). Trong trường hợp xấu nhất, hàng đợi có thể tăng đến kích thước của tầng rộng nhất, là O(n).

Thuật toán

Đưa chỉ số gốc 0 vào hàng đợi.
Bắt đầu một lượt bằng cách lưu độ dài hàng đợi vào s.
Lấy s chỉ số ra khỏi hàng đợi. Với mỗi chỉ số i, đưa 2i+1 vào hàng đợi, sau đó đưa 2i+2 vào hàng đợi nếu chúng nhỏ hơn độ dài mảng và không phải là -1.
Thêm giá trị của chỉ số cuối cùng được lấy ra trong lượt đó.
Lặp lại cho đến khi hàng đợi rỗng, rồi trả về đáp án.

from collections import deque


def rightSideView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == size - 1:
                view.append(root[i])  # the last node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

Duyệt theo chiều sâu, nút con bên phải trước

Ý tưởng

Duyệt theo chiều sâu, thử nút con bên phải trước nút con bên trái và mang theo độ sâu, bắt đầu từ 0 ở nút gốc. Lần đầu tiên lượt duyệt đến độ sâu d, đáp án có đúng d giá trị. Khi đó, thêm giá trị của nút vào đáp án và bỏ qua mọi nút khác ở cùng độ sâu.

Nút đầu tiên đó là nút ngoài cùng bên phải: mỗi khi hai đường đi đến một tầng tách ra, lượt duyệt đi theo nhánh phải xuống tận đáy rồi mới quay lại nhánh trái. Ở ví dụ 1, lượt duyệt đi qua 5, 9, 1, 2, 4, 7, 3: bỏ qua 2, 4 và 7 vì độ sâu của chúng đã có giá trị, rồi thêm 3.

Mỗi nút được duyệt một lần, thời gian O(n), với mỗi tầng có một lời gọi trên ngăn xếp, tối đa là 14.

Thuật toán

Bắt đầu với câu trả lời rỗng và nút gốc ở độ sâu 0.
Bỏ qua chỉ số vượt quá cuối mảng hoặc có giá trị -1.
Khi độ dài câu trả lời bằng độ sâu, thêm giá trị vào câu trả lời: quá trình duyệt đã đến một cấp mới và đến đó từ bên phải.
Đệ quy vào nút con bên phải 2i+2 trước, rồi đến nút con bên trái 2i+1, mỗi nút sâu hơn một cấp.
Trả về câu trả lời.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

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

Chỉ đi theo các nút con bên phải từ nút gốc. Ví dụ 1 cho kết quả [5, 9, 1] và bỏ sót 3; ví dụ 2 cho kết quả [6].
Đọc vị trí cuối cùng của mỗi mức, root[2^(d+1)-2]. Trong ví dụ 2, chỉ số 6 chứa -1; nút nhìn thấy được là 8 ở chỉ số 3.
Bỏ qua việc kiểm tra độ dài ở vị trí nút con. Trong ví dụ 1, 3 là phần tử cuối cùng, nên các vị trí nút con 17 và 18 không tồn tại.
Đưa nút con bên phải vào hàng đợi trước, đồng thời giữ lại nút cuối cùng của mỗi lượt. Cách này thu được hình chiếu bên trái, [5, 2, 7, 3].
Để các nút xuất hiện sau ghi đè các nút xuất hiện trước trong quá trình duyệt từ phải sang trái, cách này cũng cho ra hình chiếu bên trái.

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

Độ phức tạp thời gian và không gian của bài toán nhìn cây nhị phân từ phía bên phải là bao nhiêu?

Độ phức tạp thời gian là O(n) với n nút, và không lời giải nào có thể bỏ qua nút, vì nút ngoài cùng bên phải của một tầng có thể nằm ở bất kỳ vị trí nào. Độ phức tạp không gian là O(w) cho hàng đợi, trong đó w là độ rộng lớn nhất của một tầng, hoặc O(h) cho cách duyệt ưu tiên bên phải trên cây có h tầng.

Liệu tìm kiếm theo chiều sâu ưu tiên trái có giải được bài này không?

Đúng, nếu bạn ghi đè thay vì giữ giá trị đầu tiên. Cách duyệt từ trái sang phải sẽ gặp các nút ở mỗi tầng theo thứ tự từ trái sang phải, vì vậy hãy lưu giá trị của từng nút ở độ sâu của nó và để các nút xuất hiện sau thay thế các nút trước đó. Cuối cùng, mỗi độ sâu sẽ có giá trị ngoài cùng bên phải. Cách này vẫn có độ phức tạp O(n), nhưng ghi một lần cho mỗi nút.

Nên dùng thuật toán tìm kiếm theo chiều rộng hay theo chiều sâu ở đây?

Cả hai đều tuyến tính. Duyệt theo chiều rộng tuân theo định nghĩa, mỗi lượt duyệt một cấp. Duyệt theo chiều sâu chỉ giữ lại đường đi hiện tại, giúp tiết kiệm bộ nhớ trên cây rộng, và dạng đệ quy của nó ngắn hơn vài dòng.

def rightSideView(root):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Đầu ra mong đợi

[5, 9, 1, 3]