Diameter 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 tầng. 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 một vị trí trống, và mảng có thể kết thúc bằng các phần tử -1 thừa. Hãy trả về đường kính của cây: số cạnh trên đường đi dài nhất giữa hai nút bất kỳ. Đường đi có thể đi qua gốc hoặc chỉ nằm trong một cây con.
Hàm
- treeinteger-array
- cây nhị phân theo thứ tự từng mức, dùng -1 cho vị trí trống
- Trả vềinteger
- số cạnh trên đường đi dài nhất giữa hai nút
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. - 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 = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
- Đầu ra
- 4
- Giải thích
- Đường đi
7,4,3,8,6có năm nút và bốn cạnh. Đường đi rẽ tại nút gốc: ba cạnh xuống bên trái, một cạnh xuống bên phải.
- Đầu vào
- tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
- Đầu ra
- 4
- Giải thích
- Đường đi
3,1,5,9,4có bốn cạnh và rẽ tại5ở chỉ số1. Nút gốc không có nút con bên phải, nên đường đi qua nút này chỉ có ba cạnh.
- Đầu vào
- tree = [6, -1, -1]
- Đầu ra
- 0
- Giải thích
- Một nút đơn lẻ không có cạnh nào. Đường đi dài nhất chỉ gồm nút đó, có độ dài
0.
Câu hỏi mở rộng
Bạn sẽ trả về đường đi đó như thế nào, gồm các giá trị nút từ đầu này đến đầu kia của đường kính?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Mỗi đường đi trong cây đều có một nút cao nhất, nơi đường đi chuyển từ hướng lên sang hướng xuống. Nếu biết nút đó, đường đi qua nó có thể dài đến đâu?
Một đường đi rẽ tại nút (node)
isẽ đi xuống cây con bên trái (left subtree) rồi đi xuống cây con bên phải. Trong trường hợp tốt nhất, độ dài của đường đi bằng tổng chiều cao (height) của nút con bên trái và nút con bên phải, trong đó chiều cao là số nút trên đường đi xuống dài nhất và vị trí trống có chiều cao0.Tính chiều cao từ dưới lên trong một lượt duyệt hậu thứ tự: chiều cao của một nút là
1 + max(left, right). Khi cóleftvàrighttại một nút, hãy cập nhật đáp án bằngleft + right.
Lời giải
Đường đi dài nhất không nhất thiết phải đi qua nút gốc. Mỗi đường đi có một nút cao nhất, nơi đường đi đổi hướng, và đường đi dài nhất đổi hướng tại một nút có độ dài bằng tổng chiều cao nhánh trái và nhánh phải, tính theo số cạnh. Một lượt duyệt hậu thứ tự tính chiều cao của từng nút từ dưới lên và kiểm tra mọi điểm đổi hướng, với độ phức tạp O(n).
Đo mọi cặp nút
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Đo khoảng cách giữa từng cặp nút. Cha của chỉ số i là (i-1)/2, làm tròn xuống, nên khoảng cách giữa các chỉ số a và b là số lần bạn thay chỉ số lớn hơn bằng cha của nó trước khi chúng gặp nhau. Chỉ số lớn hơn không bao giờ ở cấp cao hơn, nên nó không bao giờ vượt qua điểm gặp nhau. Với 9 và 2 trong ví dụ đầu tiên: 9 đến 4 đến 1, 2 đến 0, 1 đến 0, tổng cộng bốn bước.
Một cây đầy đủ gồm 16383 nút có khoảng 1.3 × 10^8 cặp, mỗi cặp cần tối đa 26 bước: hàng tỷ bước để có một đáp án.
Thuật toán
- Thu thập chỉ số của tất cả các nút thực.
- Với mỗi cặp
(a, b), đặtedges = 0và lặp lại cho đến khia == b: thay chỉ số lớn hơn bằng nút cha của nó rồi cộng thêm1vàoedges. - Giữ lại giá trị
edgeslớn nhất mà bạn thấy và trả về giá trị đó.
def diameterOfBinaryTree(tree):
nodes = [i for i, value in enumerate(tree) if value != -1]
best = 0
for x in range(len(nodes)):
for y in range(x + 1, len(nodes)):
a, b = nodes[x], nodes[y]
edges = 0
while a != b:
# A larger index is never higher up, so climb from it.
if a > b:
a = (a - 1) // 2
else:
b = (b - 1) // 2
edges += 1
best = max(best, edges)
return bestĐo cả hai chiều cao tại mỗi nút
Ý tưởng
Gọi height(c) là số nút trên đường đi dài nhất hướng xuống từ c, với giá trị 0 cho vị trí trống. Khi đó, đường đi dài nhất rẽ tại nút i có height(2*i+1) + height(2*i+2) cạnh, mỗi nút bên dưới điểm rẽ tạo thành một cạnh. Hãy thử mọi nút làm điểm rẽ và giữ lại kết quả tốt nhất. Trong ví dụ thứ hai, nút 5 ở chỉ số 1 có chiều cao 2 ở mỗi bên, tạo thành bốn cạnh, trong khi nút gốc chỉ cho kết quả 3 + 0.
Mỗi lần gọi hàm tính chiều cao sẽ duyệt toàn bộ cây con, và mỗi nút lại được duyệt thêm một lần cho mỗi nút tổ tiên, nên độ phức tạp là O(n·h). Với h ≤ 14, cách này chạy nhanh, nhưng trên cây dạng chuỗi, độ phức tạp tăng thành O(n²).
Thuật toán
- Viết
height(i):0cho vị trí trống, nếu không thì1 + max(height(2*i+1), height(2*i+2)). - Với mỗi nút thực
i, tínhheight(2*i+1) + height(2*i+2). - Trả về tổng lớn nhất trong các tổng này.
def diameterOfBinaryTree(tree):
n = len(tree)
def height(i):
# Nodes on the longest downward path from i; an empty spot has 0.
if i >= n or tree[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
best = 0
for i in range(n):
if tree[i] != -1:
# The longest path that turns at node i goes down both sides.
best = max(best, height(2 * i + 1) + height(2 * i + 2))
return bestMột lượt duyệt hậu tự trên các chiều cao
Ý tưởng
Chiều cao của một nút chỉ cần chiều cao của các nút con, cũng là hai con số mà bước kiểm tra điểm rẽ sử dụng. Duyệt hậu thứ tự xử lý xong cả hai nút con trước nút cha, nên tại mỗi nút, bạn có left và right: cập nhật đáp án bằng left + right, rồi trả về 1 + max(left, right) cho nút cha.
Trong ví dụ đầu tiên, 7 trả về 1, 4 trả về 2 và 3 trả về 3. 6 trả về 1, nên tại nút gốc, left + right = 3 + 1 = 4. Mỗi nút được thăm một lần: thời gian O(n), và độ sâu của đệ quy là O(h).
Thuật toán
- Đặt
best = 0và viếtheight(i). Nếu vị trí trống, trả về0. - Tính
left = height(2*i+1)vàright = height(2*i+2). - Đặt
bestbằng giá trị lớn hơn giữabestvàleft + right. - Trả về
1 + max(left, right). - Gọi
height(0)và trả vềbest.
def diameterOfBinaryTree(tree):
n = len(tree)
best = 0
def height(i):
# Returns the height of node i and updates best on the way back up.
nonlocal best
if i >= n or tree[i] == -1:
return 0
left = height(2 * i + 1)
right = height(2 * i + 2)
best = max(best, left + right) # the longest path that turns at node i
return 1 + max(left, right)
height(0)
return best
Lỗi thường gặp và trường hợp biên
- Đếm nút thay vì cạnh. Đường đi
7,4,3,8,6có năm nút nhưng độ dài là4. - Chỉ đo qua nút gốc. Trong ví dụ thứ hai, cách này cho kết quả là ba, nhưng đáp án là bốn.
- Trả về đường kính từ lời gọi đệ quy. Nút cha cần chiều cao, hãy lưu đường kính trong một biến riêng.
- Dùng lẫn lộn các quy ước tính chiều cao. Nếu chiều cao tính số nút và vị trí trống có giá trị
0, kết quả làleft + rightcạnh. Nếu chiều cao tính số cạnh, vị trí trống cần có giá trị-1và kết quả làleft + right + 2. Dùng lẫn lộn hai quy ước sẽ khiến kết quả lệch một hoặc hai đơn vị. - Đọc vượt quá cuối mảng. Nút lá gần cuối mảng có chỉ số con vượt quá phần tử cuối cùng, hãy xem chúng là các vị trí trống.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Diameter of Binary Tree là bao nhiêu?
Lời giải duyệt hậu tự ghé thăm mỗi nút một lần: tốn thời gian O(n) và không gian bổ sung O(h) cho đệ quy, trong đó h là chiều cao. Tính chiều cao riêng tại mỗi nút tốn O(n·h), tương đương O(n²) với cây có hình dạng như một chuỗi.
Đường kính của cây nhị phân có luôn đi qua nút gốc không?
Không. Đường đi dài nhất có thể nằm bên trong một cây con, chẳng hạn khi nút gốc có một nhánh ngắn và một cây con sâu, nhiều nhánh ở phía bên kia. Vì vậy, bạn kiểm tra left + right tại mọi nút.
Làm thế nào để tìm đường kính của cây nhị phân mà không dùng đệ quy?
Đi qua các nút sao cho mọi nút con đều đứng trước nút cha: đẩy nút gốc vào ngăn xếp, lấy các nút ra và thêm vào danh sách, đồng thời đẩy các nút con của chúng vào ngăn xếp, sau đó duyệt ngược danh sách. Lưu chiều cao của mỗi nút vào một mảng và cập nhật kết quả bằng chiều cao của hai nút con tại mỗi nút. Độ phức tạp thời gian vẫn là O(n).
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 diameterOfBinaryTree(tree):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Đầu ra mong đợi
4