Boundary Traversal of Binary Tree
Mảng root chứa một cây nhị phân theo thứ tự từng tầng: gốc ở chỉ số 0, các nút con của chỉ số i ở 2i+1 (bên trái) và 2i+2 (bên phải), dùng -1 cho vị trí trống và có thể có thêm các phần tử -1 ở cuối. Nút lá là nút không có nút con.
Trả về đường biên theo chiều ngược kim đồng hồ, bắt đầu từ gốc:
- Gốc.
- Đường biên bên trái, từ trên xuống dưới: bắt đầu từ nút con bên trái của gốc, đi đến nút con bên trái nếu có, nếu không thì đi đến nút con bên phải. Dừng trước nút lá.
- Mọi nút lá, từ trái sang phải.
- Đường biên bên phải, từ dưới lên trên: đối xứng với đường biên bên trái, bắt đầu từ nút con bên phải của gốc.
Không liệt kê nút nào hai lần, vì vậy cây chỉ có một nút thì chỉ trả về gốc.
Hàm
- rootinteger-array
- cây nhị phân theo thứ tự từng mức, với -1 cho vị trí trống
- Trả vềinteger-array
- các giá trị biên, ngược chiều kim đồng hồ tính từ gốc
Ràng buộc
1 ≤ root.length ≤ 32767- Mỗi
root[i]là-1hoặc một giá trị thỏa mãn0 ≤ root[i] ≤ 105. 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ử
-1thừ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. - Giá trị của các nút là khác nhau.
Ví dụ
- Đầu vào
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Đầu ra
- [7, 3, 1, 4, 6, 8, 9]
- Giải thích
- Sau nút gốc
7, biên trái là3: nút con1của nó là một nút lá. Các nút lá là1,4,6,8. Biên phải là9, nằm phía trên nút lá8.
- Đầu vào
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Đầu ra
- [10, 4, 6, 5, 8]
- Giải thích
4không có nút con bên trái, nên ranh giới bên trái chuyển sang6, rồi dừng ở nút lá5. Tiếp theo là các nút lá5,8. Nút gốc không có nút con bên phải.
- Đầu vào
- root = [3]
- Đầu ra
- [3]
- Giải thích
- Gốc là toàn bộ cây. Gốc được liệt kê một lần, không được liệt kê lại như một nút lá.
Câu hỏi mở rộng
Bạn sẽ liệt kê đường bao theo chiều kim đồng hồ như thế nào: nút gốc, cạnh phải từ trên xuống dưới, các nút lá từ phải sang trái, rồi cạnh trái từ dưới lên trên?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Chia câu trả lời thành bốn phần: gốc, cạnh trái, các nút lá, cạnh phải. Phần nào là một đường đi duy nhất xuống cây, phần nào cần duyệt toàn bộ cây?
Mỗi cạnh là một đường đi: bắt đầu từ nút con của nút gốc, tiếp tục đi đến nút con ở phía đó, hoặc sang nút con còn lại nếu phía đó không có nút con. Các nút lá theo thứ tự từ trái sang phải được xác định bằng cách duyệt theo chiều sâu (depth-first), ưu tiên cây con bên trái. Hãy chú ý các điểm nối: nút lá nơi một cạnh kết thúc vẫn thuộc danh sách nút lá.
Đi xuống từ chỉ số
1và thêm từng nút không phải nút lá. Sau đó, thêm từng nút lá theo thứ tự tiền thứ tự. Tiếp theo, đi xuống từ chỉ số2, thu thập từng nút không phải nút lá rồi thêm danh sách đó theo thứ tự ngược lại.
Lời giải
Đáp án ghép bốn phần: nút gốc, đường đi dọc theo cạnh trái, các nút lá từ trái sang phải và đường đi dọc theo cạnh phải theo thứ tự ngược lại. Ở các điểm nối, mỗi nút lá ở cuối một cạnh và nút gốc nếu là nút lá chỉ được liệt kê một lần.
Đi qua riêng từng phần trong ba phần
Ý tưởng
Mỗi cạnh là một đường đi: bắt đầu từ nút con của nút gốc, liệt kê các nút cho đến khi nút tiếp theo sẽ là nút lá, vì phần liệt kê các nút lá sẽ xử lý nút đó. Duyệt theo thứ tự trước, đi sang trái trước rồi mới sang phải, sẽ gặp các nút lá theo thứ tự từ trái sang phải, vì mọi nút trong cây con bên trái đều nằm bên trái cây con bên phải, bất kể độ sâu. Thu thập cạnh phải từ trên xuống rồi nối thêm theo thứ tự ngược lại.
Mỗi cạnh đi theo một đường duy nhất và lượt duyệt các nút lá thăm mỗi nút đúng một lần: độ phức tạp thời gian O(n), với đệ quy sâu h cấp.
Thuật toán
- Bắt đầu từ nút gốc; nếu đó là nút lá, hãy trả về nút đó.
- Từ chỉ số
1, khi nút còn tồn tại và chưa phải là nút lá, hãy thêm nút đó rồi chuyển đến nút con bên trái, hoặc nút con bên phải nếu không có nút con bên trái. - Duyệt theo thứ tự trước, ưu tiên bên trái, bắt đầu từ các chỉ số
1và2, rồi thêm mọi nút lá. - Từ chỉ số
2, làm tương tự bước 2 nhưng ưu tiên nút con bên phải, đồng thời thu thập các nút. - Thêm các nút đã thu thập theo thứ tự ngược lại.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultMột lượt duyệt trước với các cờ ở cạnh
Ý tưởng
Gộp các lượt duyệt thành một lượt duyệt tiền thứ tự trên ngăn xếp bằng cách gán cho mỗi nút một cờ: 1 ở cạnh trái, 2 ở cạnh phải, 0 ở bên trong. Các nút con của nút gốc bắt đầu với 1 và 2. Nút nằm ở cạnh truyền cờ của nó cho nút con cùng phía, hoặc cho nút con duy nhất; mọi nút con còn lại nhận 0. Trong ví dụ thứ hai, cờ 1 truyền từ 4 sang 6, rồi sang 5.
Khi các nút lần lượt được lấy khỏi ngăn xếp, thêm mọi nút lá và mọi nút không phải lá mang cờ 1; thu thập các nút không phải lá mang cờ 2 và thêm chúng theo thứ tự ngược ở cuối. Duyệt tiền thứ tự đi qua mọi nút ở cạnh trái trước bất kỳ nút lá nào, vì cạnh chỉ rẽ phải ở nơi không có gì nằm bên trái nó.
Thuật toán
- Bắt đầu từ nút gốc. Đẩy nút con bên phải cùng cờ
2vào ngăn xếp, rồi đẩy nút con bên trái cùng cờ1. - Lấy một nút ra khỏi ngăn xếp. Thêm nút đó vào danh sách kết quả nếu nó là nút lá hoặc có cờ
1; thêm nút không phải nút lá có cờ2vào danh sách bên phải. - Đẩy nút con bên phải của nó, rồi nút con bên trái, mỗi nút cùng cờ mà quy tắc quy định.
- Khi ngăn xếp trống, thêm danh sách bên phải theo thứ tự đảo ngược.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Lỗi thường gặp và trường hợp biên
- Liệt kê một nút hai lần. Lượt duyệt cạnh không dừng trước khi đến lá sẽ liệt kê
1hai lần trong ví dụ 1, và cây chỉ có một nút không được liệt kê lại nút gốc như một nút lá. - Coi nút đầu tiên ở mỗi cấp là ranh giới trái. Nếu nút con trái của nút gốc là nút lá và cây con bên phải sâu hơn, các cấp sâu hơn bắt đầu bằng các nút thuộc cây con bên phải, nhưng ranh giới trái lại trống.
- Chỉ đi theo các nút con trái. Trong ví dụ 2, ranh giới phải đi từ
4đến nút con phải6. - Thu thập các nút lá theo từng cấp. Khi đó, ví dụ 1 cho kết quả
1,8,4,6. - Trong Lua và R, giữ chỉ số nút bắt đầu từ 0 để thực hiện phép tính
2i+1và đọcroot[i + 1].
Câu hỏi thường gặp3
Phép duyệt biên của cây nhị phân là gì?
Nó liệt kê các nút của cây theo chiều ngược kim đồng hồ: nút gốc, cạnh trái từ trên xuống dưới, các nút lá từ trái sang phải và cạnh phải từ dưới lên trên. Các cạnh không bao gồm những nút lá, vì vậy không nút nào xuất hiện hai lần.
Độ phức tạp thời gian của phép duyệt biên là bao nhiêu?
O(n). Hai lượt duyệt ở hai cạnh lần lượt đi theo một đường đi, còn lượt duyệt các nút lá ghé thăm mỗi nút đúng một lần. Bộ nhớ phụ là O(h) cho đệ quy hoặc ngăn xếp.
Biên trái có luôn đi theo các nút con bên trái không?
Không. Đường biên di chuyển đến nút con bên trái nếu có, nếu không thì đến nút con bên phải: đây là đường đi ngoài cùng mà bạn thấy từ bên trái. Nếu nút gốc không có nút con bên trái, đường biên trái sẽ trố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 boundaryTraversal(root):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Đầu ra mong đợi
[7, 3, 1, 4, 6, 8, 9]