Left View of Binary Tree

+10

Bạn nhận được một cây nhị phân dưới dạng mảng root theo thứ tự heap: gốc ở 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ảng có thể kết thúc bằng các phần tử -1 bổ sung.

Đứng ở bên trái cây. Ở mỗi tầng, bạn nhìn thấy một nút, nút ngoài cùng bên trái; các nút còn lại trong tầng bị nó che khuất. Trả về các giá trị bạn nhìn thấy, từ tầng trên cùng xuống dưới.

Hàm

leftView(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 trá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ị của 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 bổ sung 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 tầng.

Ví dụ

Đầu vào: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Đầu ra: [3, 8, 6, 1]
Giải thích: 8 là một nút lá, vì vậy tầng thứ ba và thứ tư chỉ chứa 6 (chỉ số 6) và 1 (chỉ số 13), cả hai đều nằm dưới nút con bên phải 5. Bạn vẫn thấy chúng: [3, 8, 6, 1].

Đầu vào: root = [10, -1, -1]
Đầu ra: [10]
Giải thích: Chỉ số 1 và 2 chứa -1, nên 10 không có nút con và chế độ xem chỉ có nút gốc.

Đầu vào: root = [1, 2, 3, 4, 5, 6, 7]
Đầu ra: [1, 2, 4]
Giải thích: Một cây đầy đủ có ba cấp. Các vị trí ngoài cùng bên trái ở các cấp có chỉ số 0, 1 và 3, chứa 1, 2 và 4.

Câu hỏi mở rộng

Cấp độ d điền các chỉ số từ 2^d-1 đến 2^(d+1)-2. Bạn có thể xây dựng chế độ xem bằng cách quét các phạm vi đó mà không dùng hàng đợi hay đệ quy không? Cách đó tốn bao nhiêu khi dùng mảng được đệm?

Lời giải

Lần theo các nút con bên trái từ nút gốc sẽ thất bại khi cây con bên trái thấp hơn: trong ví dụ đầu tiên, bạn nhìn thấy các tầng thấp hơn qua cây con bên phải. Bạn cần nút đầu tiên ở mỗi tầng. Tìm kiếm theo chiều rộng sẽ đưa bạn qua từng tầng từ trái sang phải; cách duyệt theo chiều sâu, ưu tiên đi sang trái, sẽ gặp nút ngoài cùng bên trái của mỗi tầng trước tiên.

Duyệt theo chiều rộng, nút đầu tiên ở mỗi cấp

Ý tưởng

Hàng đợi được xử lý theo từng lượt sẽ đưa cho bạn các tầng, từng tầng một. Khi bắt đầu mỗi lượt, hàng đợi chỉ chứa đúng một tầng, theo thứ tự từ trái sang phải, vì mọi nút con được thêm trong lượt đó đều nằm phía sau tầng ấy. Lấy ra số lượng chỉ số tương ứng, thêm các nút con của từng nút vào hàng đợi, bắt đầu từ nút bên trái, rồi giữ lại giá trị đầu tiên.

Trong ví dụ đầu tiên, các lượt là [3], [8, 5], [6] và [1], và chúng lần lượt giữ lại 3, 8, 6 và 1. 8 không thêm gì, vì các vị trí nút con 3 và 4 của nó chứa -1.

Mỗi nút vào và rời khỏi hàng đợi một lần: độ phức tạp thời gian O(n). Hàng đợi chứa toàn bộ một tầng, tối đa 8192 chỉ số trong cây đầy đủ có 14 tầng.

Thuật toán

Bắt đầu một hàng đợi chứa chỉ số 0 và một câu trả lời rỗng.
Khi hàng đợi chưa rỗng, gọi kích thước của nó là s rồi xóa s chỉ số. Thêm giá trị của chỉ số đầu tiên vào câu trả lời.
Với mỗi chỉ số i đã xóa, thêm 2i+1, rồi 2i+2 vào hàng đợi, bỏ qua các chỉ số vượt quá cuối và các phần tử bằng -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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, ưu tiên nút con bên trái

Ý tưởng

Duyệt theo chiều sâu, đi qua cây con bên trái trước cây con bên phải và truyền độ sâu của từng nút. Nút đầu tiên mà lượt duyệt chạm đến ở độ sâu d là nút ngoài cùng bên trái ở mức d. Xét nút ngoài cùng bên trái x ở một mức và một nút bất kỳ y nằm bên phải nó: tại nút cuối cùng chung trên đường đi của chúng, x đi sang trái còn y đi sang phải, và lượt duyệt hoàn tất nhánh trái trước khi rẽ sang phải.

Lượt duyệt đi xuống từng mức một, nên khi lần đầu chạm đến độ sâu d, đáp án có đúng d giá trị. Ghi lại một nút khi d bằng độ dài của đáp án; không cần tập hợp các độ sâu đã duyệt.

Mỗi nút được thăm một lần, thời gian O(n), bộ nhớ lưu một lời gọi cho mỗi mức, tối đa 14 ở đây. Phiên bản R tự quản lý ngăn xếp và đẩy nút con bên phải vào trước nút con bên trái.

Thuật toán

Tạo một đáp án rỗng và gọi visit(0, 0).
Trong visit(i, d), trả về ngay nếu i nằm ngoài mảng hoặc root[i] là -1.
Nếu d bằng độ dài của đáp án, đường đi đã lần đầu tiên đến mức d: thêm root[i].
Gọi visit(2i+1, d+1), sau đó gọi visit(2i+2, d+1).
Trả về đáp án sau khi lời gọi đầu tiên kết thúc.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, 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 trái từ nút gốc. Trong ví dụ đầu tiên, cách này dừng ở 8 và bỏ qua 6 và 1.
Đọc vị trí đầu tiên ở mỗi tầng, root[2^d-1]. Trong ví dụ đầu tiên, vị trí đầu tiên của tầng thứ ba, chỉ số 3, chứa -1, trong khi nút duy nhất của tầng này nằm ở chỉ số 6.
Thăm nút con bên phải trước trong quá trình duyệt theo chiều sâu. Khi đó, nút đầu tiên gặp ở mỗi tầng là nút ngoài cùng bên phải.
Đọc nút con mà không kiểm tra giới hạn. 1 ở chỉ số 13 có các vị trí nút con là 27 và 28, nằm ngoài mảng 14 phần tử.

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

Khung nhìn bên trái có giống với ranh giới bên trái của cây không?

Không. Biên trái là một đường đi: bắt đầu từ nút con trái của nút gốc, đi sang trái nếu có thể, nếu không thì đi sang phải, rồi dừng trước một nút lá. Hình chiếu bên trái lấy một nút ở mỗi cấp từ bất kỳ nhánh nào. Trong ví dụ đầu tiên, biên trái trống vì 8 là nút lá, nhưng hình chiếu bên trái hiển thị 8, 6 và 1.

Độ phức tạp thời gian và không gian của hình chiếu bên trái là bao nhiêu?

Cả hai lời giải đều duyệt qua mỗi nút một lần, nên thời gian là O(n). Hàng đợi duyệt theo chiều rộng chứa một tầng, khoảng một nửa số nút của cây đầy đủ. Cách duyệt ưu tiên bên trái giữ một lời gọi cho mỗi tầng, O(h) với h tầng.

Làm thế nào để thay đổi lời giải để có được giao diện đúng?

Trong phiên bản tìm kiếm theo chiều rộng, hãy giữ giá trị cuối cùng của mỗi lượt thay vì giá trị đầu tiên. Trong phiên bản tìm kiếm theo chiều sâu, hãy duyệt nút con bên phải trước nút con bên trái; khi đó, nút đầu tiên mà quá trình duyệt chạm tới ở mỗi tầng sẽ là nút ngoài cùng bên phải.

def leftView(root):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Đầu ra mong đợi

[3, 8, 6, 1]