Binary Tree Level Order Traversal
Mảng (array) tree 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 vị trí trống và có thể có thêm các phần tử -1 ở cuối.
Trả về các giá trị nút theo từng cấp: một danh sách cho mỗi cấp, từ gốc xuống cấp sâu nhất, mỗi danh sách chứa các giá trị theo thứ tự từ trái sang phải.
Hàm
- treeinteger-array
- cây theo thứ tự heap, với -1 cho vị trí trống
- Trả vềinteger-2d-array
- mỗi cấp độ có một danh sách giá trị, bắt đầu từ cấp cao nhất, lần lượt từ trái sang phải
Ràng buộc
1 ≤ tree.length ≤ 32767- Mỗi
tree[i]là-1hoặc một giá trị thỏa mãn0 ≤ tree[i] ≤ 1000. tree[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ử
-1thừa sau nút cuối cùng. - 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.
Ví dụ
- Đầu vào
- tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- Đầu ra
- [[4], [9, 2], [6, 8, 5], [3]]
- Giải thích
- Chỉ số 3 trống, nên
9chỉ có nút con bên phải là6. Tầng thứ ba gồm6,8,5, còn3ở chỉ số 9 nằm bên dưới6và đứng một mình ở tầng thứ tư.
- Đầu vào
- tree = [7, -1, -1]
- Đầu ra
- [[7]]
- Giải thích
- Cả hai nút con của nút gốc đều là
-1, nên cây chỉ có nút7và có một cấp.
- Đầu vào
- tree = [1, 3, -1, 5, -1, -1, -1]
- Đầu ra
- [[1], [3], [5]]
- Giải thích
- Mỗi nút chỉ có một nút con bên trái:
3ở chỉ số 1 và5ở chỉ số 3. Mỗi tầng chứa một giá trị, còn các phần tử-1ở cuối không thêm gì cả.
Câu hỏi mở rộng
Bạn có thể trả về các mức theo thứ tự zíc zắc, mức đầu tiên từ trái sang phải, mức thứ hai từ phải sang trái, cứ thế tiếp tục, mà không sắp xếp bất kỳ mức nào không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Các nút con ở chỉ số
inằm tại2*i+1và2*i+2. Nếu bạn luôn thăm các nút gần gốc nhất trước, rồi đi từ trái sang phải trong số các nút đó, bạn sẽ gặp các nút theo thứ tự nào?Hàng đợi trả về các nút theo đúng thứ tự bạn thêm chúng vào. Nếu bạn thêm các nút con khi lấy một nút ra, các nút sẽ được lấy ra lần lượt theo từng cấp. Điều còn lại là xác định nơi một cấp kết thúc và cấp tiếp theo bắt đầu.
Khi bắt đầu mỗi vòng, hàng đợi chứa chính xác một cấp. Đọc kích thước
s, lấy rasnút vào một danh sách mới, rồi thêm các nút con của chúng, ưu tiên nút bên trái, bỏ qua-1và các chỉ số vượt quá giới hạn. Dừng khi hàng đợi trống.
Lời giải
Mỗi cấp phải được tạo thành một danh sách riêng theo thứ tự từ trái sang phải. Tìm kiếm theo chiều rộng dùng hàng đợi sẽ thăm các nút theo thứ tự đó. Ở đầu mỗi lượt, hàng đợi chứa chính xác một cấp, vì vậy kích thước của hàng đợi cho biết cần lấy bao nhiêu nút. Cách duyệt theo chiều sâu có theo dõi độ sâu của mỗi nút cũng hoạt động.
Duyệt theo chiều sâu, lưu theo độ sâu
Ý tưởng
Duyệt cây theo chiều sâu, truyền độ sâu cho từng nút, với gốc có độ sâu 0, rồi giữ một danh sách cho mỗi độ sâu. Nút ở độ sâu d sẽ thêm giá trị của nó vào danh sách d, tạo danh sách đó nếu đây là nút đầu tiên được thấy ở độ sâu này.
Mỗi danh sách được sắp xếp từ trái sang phải vì lượt duyệt hoàn tất cây con bên trái của một nút trước khi đi vào cây con bên phải. Trong hai nút cùng độ sâu, nút có đường đi rẽ trái tại điểm hai đường đi tách nhau sẽ được duyệt trước. Trong ví dụ 1, thứ tự duyệt 4, 9, 6, 3, 2, 8, 5 tạo ra [4], [9, 2], [6, 8, 5], [3].
Mỗi nút được duyệt một lần: thời gian O(n), với độ sâu đệ quy bằng độ sâu của cây, tối đa 14 cấp.
Thuật toán
- Tạo một danh sách cấp độ trống.
- Thăm nút gốc với độ sâu 0.
- Tại nút
ivới độ sâud, dừng lại nếuivượt quá cuối hoặctree[i]là-1. - Nếu chỉ có
ddanh sách, hãy thêm một danh sách trống. Thêmtree[i]vào danh sáchd. - Thăm
2i+1, rồi2i+2, cả hai đều với độ sâud+1.
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levelsDuyệt theo chiều rộng, mỗi vòng một cấp
Ý tưởng
Lấy một nút ra khỏi hàng đợi rồi đưa các nút con của nó vào, bắt đầu từ bên trái. Các nút ở tầng d+1 chỉ được đưa vào khi các nút ở tầng d rời đi, vì vậy các nút rời khỏi hàng đợi lần lượt theo từng tầng, từ trái sang phải.
Để chia luồng đó thành các tầng, hãy đọc kích thước hàng đợi ở đầu mỗi lượt. Tầng trước đã rời đi và chưa có nút nào ở tầng tiếp theo vào hàng đợi, nên hàng đợi chỉ chứa đúng các nút của tầng hiện tại. Lấy số nút đó thành một hàng; các nút con của chúng sẽ chờ đến lượt tiếp theo. Trong ví dụ 1, các lượt lấy lần lượt 1, 2, 3 và 1 nút.
Mỗi nút vào và rời khỏi hàng đợi một lần: thời gian O(n). Hàng đợi chứa số nút xấp xỉ một tầng, nhiều nhất là 8,192 nút ở tầng sâu nhất của cây 14 tầng đầy đủ.
Thuật toán
- Đưa chỉ số
0của nút gốc vào hàng đợi. - Khi hàng đợi chưa rỗng, đọc kích thước
scủa hàng đợi và tạo một hàng trống. - Lấy ra
schỉ số. Với mỗi chỉ sối, thêmtree[i]vào hàng. - Thêm
2i+1, rồi2i+2, vào hàng đợi nếu chỉ số nằm trong mảng và giá trị tại đó không phải-1. - Thêm hàng vào đáp án rồi bắt đầu lượt tiếp theo.
from collections import deque
def levelOrder(tree):
n = len(tree)
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(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
Lỗi thường gặp và trường hợp biên
- Đọc kích thước của hàng đợi trong khi lấy hết phần tử ra. Trong
while (j < queue.length), độ dài tăng lên khi các nút con được thêm vào, nên cấp tiếp theo lọt vào hàng hiện tại. - Thêm nút con bên phải trước nút con bên trái, hoặc duyệt cây con bên phải trước. Khi đó, cấp thứ hai của Ví dụ 1 sẽ là
[2, 9]. - Bỏ qua bước kiểm tra giới hạn
child < n. Các nút con của những nút ở sâu nhất nằm ngoài phạm vi của mảng. - Xóa phần tử ở đầu danh sách mảng thông thường, thao tác này khiến nhiều ngôn ngữ dịch chuyển toàn bộ hàng đợi mỗi lần. Hãy dùng hàng đợi thực sự hoặc chỉ số đầu hàng đợi.
- Xem
-1là một nút. Giá trị này không bao giờ được thêm vào một hàng hoặc hàng đợi:[7, -1, -1]cho kết quả[[7]], không phải[[7], []].
Câu hỏi thường gặp3
Độ phức tạp thời gian của việc duyệt cây nhị phân theo thứ tự từng mức là bao nhiêu?
Cả hai lời giải đều duyệt mỗi nút một lần: thời gian O(n) với n nút. Kết quả chứa n giá trị, nên cần O(n) bộ nhớ. Ngoài ra, hàng đợi chứa số nút gần bằng số nút ở tầng rộng nhất, còn đệ quy cần bộ nhớ theo chiều cao của cây.
Làm thế nào để biết một mức kết thúc ở đâu trong tìm kiếm theo chiều rộng?
Đọc kích thước của hàng đợi ở đầu mỗi lượt và lấy đúng số nút đó. Hai cách khác cũng hiệu quả: lưu cấp độ hiện tại và cấp độ tiếp theo trong hai danh sách riêng, hoặc thêm một dấu mốc vào hàng đợi sau mỗi cấp độ.
Mảng đã được lưu sẵn theo từng cấp độ. Sao bạn không đọc nó theo từng lát?
Với định dạng này, cách làm như sau: độ sâu d, với nút gốc ở vị trí 0, bao phủ các chỉ số từ 2^d-1 đến 2^(d+1)-2. Vì vậy, hãy thu thập các giá trị không rỗng trong từng khoảng cho đến khi có một khoảng không chứa giá trị nào. Trong các cuộc phỏng vấn, người ta thường truyền các đối tượng nút có con trỏ thay thế, và chỉ hàng đợi (queue) được giữ nguyên khi chuyển sang dạng đó.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def levelOrder(tree):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Đầu ra mong đợi
[[4], [9, 2], [6, 8, 5], [3]]