Binary Tree Zigzag Level Order Traversal

+10

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

Trả về giá trị các nút theo từng tầng theo thứ tự zíc zắc: tầng của gốc từ trái sang phải, tầng tiếp theo từ phải sang trái, rồi tiếp tục luân phiên như vậy đến tầng sâu nhất. Cách này còn được gọi là duyệt theo thứ tự tầng xoắn ốc.

Hàm

zigzagLevelOrder(root: integer-array) → integer-2d-array

rootinteger-array: cây theo thứ tự heap, với -1 cho vị trí trống
Trả vềinteger-2d-array: một danh sách giá trị cho mỗi cấp, bắt đầu từ cấp cao nhất, luân phiên từ trái sang phải và từ phải sang trái

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⁴.
Giá trị các nút khác nhau.
root[0] không bao giờ là -1, vì vậy cây (tree) có ít nhất một nút.
Mảng (array) có thể kết thúc bằng các phần tử -1 bổ sung nằm 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 = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Đầu ra: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
Giải thích: Đọc từ trái sang phải, các cấp độ là 8; 12, 5; 1, 9, 14; 4, 2, 11. Cấp độ 1 và 3 chạy ngược lại: [5, 12] và [11, 2, 4].

Đầu vào: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
Đầu ra: [[1], [3, 2], [4, 5, 6, 7]]
Giải thích: Một cây đầy đủ có ba cấp: cấp giữa đảo thành [3, 2] và cấp thứ ba lại chạy từ trái sang phải. Hai phần tử -1 ở cuối là các vị trí con trống của 4.

Câu hỏi mở rộng

Bạn có thể đặt từng giá trị thẳng vào vị trí cuối cùng trong hàng của nó mà không cần đảo ngược và không cần ngăn xếp thứ hai không?

Lời giải

Các cấp độ được tạo ra bằng một thuật toán tìm kiếm theo chiều rộng thông thường. Điểm mới là hướng: cứ cách một cấp độ, thứ tự lại bị đảo ngược. Bạn có thể đảo ngược các hàng lẻ sau khi tạo xong, hoặc lưu từng cấp độ vào một ngăn xếp, nơi trả lại các phần tử theo thứ tự ngược với thứ tự thêm vào.

Duyệt theo thứ tự từng tầng, rồi đảo ngược mọi tầng xen kẽ

Ý tưởng

Hàng đợi xử lý một mức trong mỗi lượt sẽ cho ra các nút ở từng mức theo thứ tự từ trái sang phải. Đánh số các mức bắt đầu từ 0 ở nút gốc: thứ tự zigzag đọc các mức lẻ từ phải sang trái, vì vậy đảo ngược chính xác các hàng đó sẽ cho ra đáp án.

Quá trình tìm kiếm duyệt mỗi nút một lần và mỗi lần đảo ngược cũng chạm đến từng giá trị thêm một lần, nên độ phức tạp thời gian là O(n).

Thuật toán

Bắt đầu hàng đợi với chỉ số 0.
Trong mỗi lượt, lưu độ dài hàng đợi vào s, lấy ra s chỉ số để tạo thành một hàng mới, rồi thêm các nút con hiện có của từng nút vào hàng đợi, nút bên trái trước nút bên phải.
Nếu đáp án đã có số hàng lẻ, đảo ngược hàng đó.
Thêm hàng đó vào đáp án và tiếp tục cho đến khi hàng đợi trống.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

Hai ngăn xếp

Ý tưởng

Giữ cấp hiện tại trong một ngăn xếp, lấy các nút ra theo hướng đọc cấp đó, rồi đẩy các nút con của mỗi nút vừa lấy ra vào ngăn xếp thứ hai. Khi ngăn xếp hiện tại trống, ngăn xếp thứ hai chứa cấp tiếp theo.

Thứ tự đẩy giúp cách này hoạt động. Khi lấy các nút từ trái sang phải, hãy đẩy nút con bên trái rồi đến nút con bên phải của mỗi nút: nút con bên phải của nút ngoài cùng bên phải được đẩy sau cùng, nên cấp tiếp theo được lấy ra từ đầu bên phải. Khi lấy các nút từ phải sang trái, hãy đẩy nút con bên phải rồi đến nút con bên trái, và nút con bên trái của nút ngoài cùng bên trái được đẩy sau cùng.

Ví dụ 1: lấy 8 ra, đẩy 12, 5 vào. Lấy 5, 12 ra, rồi đẩy 14 từ 5 và 9, 1 từ 12 vào. Lấy 1, 9, 14 ra, rồi đẩy 4, 2 từ 9 và 11 từ 14 vào. Lấy 11, 2, 4 ra.

Mỗi nút được đẩy vào và lấy ra đúng một lần: thời gian O(n), không cần lượt đảo ngược.

Thuật toán

Đưa chỉ số 0 của nút gốc vào một ngăn xếp và bắt đầu đọc từ trái sang phải.
Khi ngăn xếp chưa rỗng, lấy từng chỉ số ra thành một hàng mới, rồi đưa các nút con hiện có của mỗi nút vừa lấy ra vào ngăn xếp thứ hai: nút trái trước rồi đến nút phải khi đọc từ trái sang phải, ngược lại thì nút phải trước rồi đến nút trái.
Thêm hàng đó vào kết quả.
Dùng ngăn xếp thứ hai làm ngăn xếp hiện tại, đảo chiều đọc rồi lặp lại.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

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

Đảo thứ tự con được đưa vào cùng một hàng đợi. Các anh chị em đổi chỗ cho nhau nhưng thứ tự của cha mẹ vẫn giữ nguyên: tầng thứ ba của ví dụ 1 có kết quả là [9, 1, 14].
Đếm các tầng bắt đầu từ 1. Mỗi lần đảo đều lệch một tầng, và ví dụ 1 cho kết quả [[8], [12, 5], [14, 9, 1], [4, 2, 11]].
Dùng cùng một thứ tự đẩy ở mọi tầng trong phiên bản dùng hai ngăn xếp. Khi đó, tầng thứ ba của ví dụ 1 được lấy ra theo thứ tự [9, 1, 14].
Đẩy các con vào ngăn xếp mà bạn vẫn đang lấy phần tử ra. Chúng sẽ được lấy ra trước phần còn lại ở tầng của cha mẹ.
Sắp xếp một hàng thay vì đảo ngược hàng đó. Tầng cuối cùng của ví dụ 1 phải là [11, 2, 4], nhưng không cách sắp xếp nào cho ra kết quả đó.

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

Sự khác biệt giữa cách duyệt zigzag và cách duyệt theo từng mức là gì?

Chúng duyệt các cấp giống nhau với cùng các nút. Duyệt theo cấp đọc từng cấp từ trái sang phải; duyệt zigzag đọc mỗi cấp thứ hai từ phải sang trái, bắt đầu từ cấp bên dưới gốc. Cả hai đều chạy trong thời gian O(n).

Việc duyệt cây theo đường zích zắc có giống với việc duyệt cây theo thứ tự xoắn ốc không?

Đúng vậy, hai tên gọi mô tả cùng một cách duyệt. Một số tài liệu bắt đầu mức thứ hai từ trái thay vì từ phải, điều này chỉ khiến các lần đổi hướng lệch đi một mức. Ở đây, mức của nút gốc đi từ trái sang phải, còn mức tiếp theo đi từ phải sang trái.

Có thể duyệt theo thứ tự mức zíc zắc bằng deque không?

Đúng vậy. Hãy giữ các nút ở mỗi cấp trong deque theo thứ tự từ trái sang phải. Ở cấp duyệt từ trái sang phải, lấy các nút ở đầu và thêm các nút con của chúng vào cuối, lần lượt từ trái sang phải. Ở cấp duyệt từ phải sang trái, lấy các nút ở cuối và thêm các nút con của chúng vào đầu, lần lượt từ phải sang trái. Số lượng nút bạn lấy khi bắt đầu một lượt vẫn xác định cấp đó.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

Đầu ra mong đợi

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]