Maximum Depth of Binary Tree
Bạn nhận được một cây nhị phân được lưu trong mảng tree theo thứ tự từng mức. 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à mảng có thể kết thúc bằng một số phần tử -1 thừa. Hãy trả về độ sâu tối đa của cây: số nút trên đường đi dài nhất từ gốc xuống một nút lá.
Hàm
- treeinteger-array
- cây nhị phân theo thứ tự mức, với -1 cho vị trí trống
- Trả vềinteger
- số lượng nút trên đường đi dài nhất từ gốc đến lá
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 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à độ sâu tối đa là
14.
Ví dụ
- Đầu vào
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Đầu ra
- 4
- Giải thích
- Đường đi dài nhất là
5,8,3,6(các chỉ số0,1,4,9), gồm 4 nút. Đường đi qua1dừng lại sau 2 nút.
- Đầu vào
- tree = [7, -1, -1]
- Đầu ra
- 1
- Giải thích
- Hai vị trí
-1là chỗ trống dành cho nút con của nút gốc. Chỉ riêng nút gốc đã tạo thành một đường đi gồm một nút, nên độ sâu là1, không phải0.
- Đầu vào
- tree = [2, -1, 9, -1, -1, -1, 4]
- Đầu ra
- 3
- Giải thích
- Nút gốc
2không có nút con bên trái. Nút con bên phải9ở chỉ số2có nút4ở chỉ số6làm nút con bên phải, tạo thành một đường đi gồm 3 nút.
Câu hỏi mở rộng
Bạn sẽ trả về các giá trị trên đường đi dài nhất từ gốc đến lá cùng với độ dài của đường đi đó như thế nào? Nếu có nhiều đường đi dài bằng nhau, bạn sẽ trả về đường đi nào?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Hãy nghĩ về nút gốc. Nếu biết độ sâu của cây con bên trái và cây con bên phải, bạn sẽ tính độ sâu của cả cây như thế nào?
Giá trị này bằng
1cộng với độ sâu lớn hơn trong hai cây con, còn vị trí trống có độ sâu0. Quy tắc này áp dụng cho mọi nút, vì vậy phép duyệt biết độ sâu của từng nút có thể tìm ra đáp án.Duy trì một ngăn xếp gồm các cặp: chỉ số nút và độ sâu của nút, bắt đầu với nút gốc ở độ sâu 1. Lấy một cặp ra khỏi ngăn xếp, ghi nhớ độ sâu lớn nhất đã gặp, rồi thêm mỗi nút con có chỉ số
2*i+1và2*i+2vào ngăn xếp nếu chỉ số đó nằm trong mảng và giá trị không phải-1, với độ sâu tăng thêm một.
Lời giải
Độ sâu được xác định bởi nhánh dài nhất, và bạn không thể biết nhánh đó là nhánh nào nếu chưa thăm mọi nút. Vì vậy, bạn cần duyệt toàn bộ cây một lần và biết độ sâu tại mỗi nút. Đệ quy, tìm kiếm theo chiều rộng từng mức và tìm kiếm theo chiều sâu với ngăn xếp riêng đều thực hiện được việc này trong một lượt.
Đệ quy trên hai cây con
Ý tưởng
Một vị trí con (child spot) có thật khi chỉ số (index) của nó nằm trong mảng (array) và giá trị (value) của nó không phải là -1. Đường đi sâu nhất (deepest path) qua một nút đi xuống cây con (subtree) sâu hơn của nút đó, vì vậy độ sâu (depth) tại chỉ số i bằng 1 cộng với độ sâu lớn hơn trong hai chỉ số 2*i+1 và 2*i+2. Vị trí trống có độ sâu là 0, điều này kết thúc đệ quy (recursion). Nút lá có độ sâu 1 + max(0, 0) = 1, rồi các giá trị tăng dần khi quay ngược lên nút gốc.
Mỗi nút được thăm một lần. Ngăn xếp lời gọi (call stack) giữ một khung (frame) cho mỗi cấp của đường đi hiện tại, O(h), tối đa là 14 ở đây.
Thuật toán
- Viết
depth(i): nếuivượt quá cuối mảng hoặctree[i]là-1, trả về0. - Nếu không, trả về
1 + max(depth(2*i+1), depth(2*i+2)). - Trả về
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Tìm kiếm theo chiều rộng, từng cấp độ
Ý tưởng
Độ sâu tối đa là số tầng, vì vậy bạn có thể đếm số tầng thay vì lần theo các đường đi. Hàng đợi duyệt các nút theo thứ tự từng tầng. Trước mỗi lượt xử lý, hãy đọc kích thước hàng đợi: những nút đó thuộc đúng một tầng, vì các nút con bạn thêm vào trong lượt xử lý sẽ đứng sau chúng. Mỗi lượt xử lý làm độ sâu tăng thêm 1. Trong ví dụ đầu tiên, các lượt xử lý là [5], [8, 1], [3] và [6], vì vậy đáp án là 4.
Hàng đợi chứa một tầng tại mỗi thời điểm, O(w) cho tầng rộng nhất. Trong cây đầy đủ có độ sâu 14, tầng đó có 8192 trong tổng số 16383 nút.
Thuật toán
- Đưa chỉ số gốc
0vào hàng đợi và đặtdepth = 0. - Trong khi hàng đợi chưa rỗng, tăng
depththêm1và đọc kích thước hàng đợi. - Lấy ra số lượng chỉ số đó. Với mỗi chỉ số, đưa các chỉ số con
2*i+1và2*i+2nằm trong mảng và không phải-1vào hàng đợi. - Khi hàng đợi rỗng, trả về
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthTìm kiếm theo chiều sâu bằng ngăn xếp tường minh
Ý tưởng
Tự quản lý một ngăn xếp gồm các cặp chỉ số nút và độ sâu, vì không có gì khác ghi nhớ một nút nằm sâu đến đâu. Bắt đầu với (0, 1), nút gốc ở độ sâu 1. Mỗi nút được đưa vào ngăn xếp một lần, kèm theo độ dài của đường đi dẫn đến nút đó, nên độ sâu lớn nhất bạn lấy ra chính là đáp án. Trong ví dụ đầu tiên, 6 được đưa vào ngăn xếp dưới dạng (9, 4).
Ngăn xếp chứa khoảng một nút anh em đang chờ xử lý ở mỗi cấp, O(h), và không có ngăn xếp lời gọi nào để bị tràn. Cùng một đoạn code hoạt động trên cây dựa trên con trỏ với độ sâu bất kỳ.
Thuật toán
- Đẩy
(0, 1)vào ngăn xếp và đặtbest = 0. - Lấy cặp
(i, depth)ra và đặtbestthành giá trị lớn hơn giữabestvàdepth. - Với mỗi chỉ số con
2*i+1và2*i+2nằm trong mảng (array) và không phải-1, hãy đẩy chỉ số đó vào ngăn xếp cùng vớidepth + 1. - Lặp lại cho đến khi ngăn xếp trống, rồi trả về
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Lỗi thường gặp và trường hợp biên
- Đếm cạnh thay vì nút.
[7, -1, -1]có độ sâu1, không phải0. - Bỏ qua bước kiểm tra giới hạn. Trong ví dụ đầu tiên,
6ở chỉ số 9 có các chỉ số con là 19 và 20, vượt quá cuối mảng. Kiểm trachild < ntrước khi đọctree[child]. - Tính độ sâu dựa trên độ dài của mảng. Các phần tử
-1ở cuối dẫn đến một mức không có nút nào:[7, -1, -1]có độ dài 3 nhưng độ sâu là 1. - Đọc kích thước của hàng đợi bên trong vòng lặp xử lý theo đợt. Các phần tử con được thêm vào trong đợt sẽ làm thay đổi kích thước, vì vậy hãy lưu kích thước trước.
- Nhầm lẫn về độ lệch trong Lua và R, nơi mảng bắt đầu từ 1. Giữ chỉ số nút bắt đầu từ 0 khi dùng
2*i+1và đọctree[i + 1].
Câu hỏi thường gặp3
Độ phức tạp thời gian của bài toán Độ sâu tối đa của cây nhị phân là gì?
Mỗi cách tiếp cận đều duyệt qua mỗi nút một lần, nên thời gian là O(n). Các phiên bản duyệt theo chiều sâu dùng thêm O(h) bộ nhớ cho đường đi hiện tại, trong đó h là độ sâu. Phiên bản duyệt theo chiều rộng dùng O(w) bộ nhớ cho tầng rộng nhất, tức khoảng một nửa số nút trong cây đầy đủ.
Bạn nên dùng DFS hay BFS để tìm độ sâu tối đa của cây nhị phân?
Cả hai đều chạy trong thời gian O(n). Tìm kiếm theo chiều sâu ngắn hơn khi viết và dùng bộ nhớ tỷ lệ thuận với độ sâu, phù hợp với cây rộng và nông. Tìm kiếm theo chiều rộng đếm trực tiếp các mức và dùng bộ nhớ tỷ lệ thuận với mức rộng nhất, phù hợp với cây sâu và hẹp. Để tìm độ sâu tối thiểu, BFS hiệu quả hơn vì có thể dừng ngay khi gặp lá đầu tiên.
Sự khác biệt giữa độ sâu và chiều cao của cây nhị phân là gì?
Độ sâu của một nút là số bước từ nút gốc đi xuống nút đó; chiều cao là số bước từ nút đó đi xuống lá sâu nhất của nó. Độ sâu tối đa của cây bằng chiều cao của nút gốc. Bài toán này đếm số nút, vì vậy một nút đơn lẻ có độ sâu là 1; nếu đếm cạnh thì kết quả ít hơn một.
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 maxDepth(tree):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Đầu ra mong đợi
4