Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm chiều rộng tối đa của bất kỳ mức nào trong cây. Ở đây chiều rộng của một mức là số lượng nút có thể chứa giữa nút ngoài cùng bên trái và nút ngoài cùng bên phải.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 2
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
tạo một bản đồ d, để giữ các giá trị tối thiểu và tối đa, giá trị nhỏ nhất ban đầu là vô cực và tối đa là 0
-
Định nghĩa một hàm dfs (). Điều này sẽ có gốc, pos:=0, depth:=0
-
nếu root là null, không trả về
-
d [depth, 0] =tối thiểu là d [depth, 0] và pos
-
d [depth, 1] =tối đa là d [depth, 1] và pos
-
dfs (bên trái của nút, 2 * vị trí, độ sâu + 1)
-
dfs (bên phải của nút, 2 * pos + 1, depth + 1)
-
Từ phương thức chính, hãy thực hiện như sau−
-
dfs (gốc)
-
mx:=0
-
cho mỗi cặp min-max trong danh sách tất cả các giá trị của d, do
-
left:=min, right:=max
-
mx:=tối đa là mx, right-lelf + 1
-
-
trả lại mx
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
from collections import defaultdict class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): d=defaultdict(lambda: [1e9,0]) def dfs(node, pos=0, depth=0): if not node: return d[depth][0]=min(d[depth][0],pos) d[depth][1]=max(d[depth][1],pos) dfs(node.left,2*pos,depth+1) dfs(node.right,2*pos+1,depth+1) dfs(root) mx=0 for interval in d.values(): l,r=interval mx=max(mx,r-l+1) return mx ob = Solution() root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))
Đầu vào
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
Đầu ra
2