Cho một cây nhị phân, tìm cây con (subtree) lớn nhất (nhiều nút nhất) là cây tìm kiếm nhị phân (BST).
Ví dụ: cây gốc có nút 12, con trái 3, con phải 5 (con trái 4, con phải 6). Cây con BST lớn nhất là cây gốc tại nút 5 (4,5,6) → in-order: 4,5,6.
Giải thuật (Duyệt post-order, kiểm tra BST)
- Duyệt post-order, tại mỗi nút thu thập danh sách giá trị in-order của cây con.
- Nếu danh sách đã sắp xếp → là BST. Cập nhật kích thước lớn nhất và nút gốc tương ứng.
- Trả về danh sách in-order để nút cha sử dụng.
Lưu ý: Cách này O(n²) do nối list. Có thể tối ưu bằng cách trả về (min, max, size, is_bst).
Mã nguồn Python
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root):
max_size = [0]
max_node = [None]
def traverse(node):
if not node:
return []
left = traverse(node.left)
right = traverse(node.right)
lst = left + [node.val] + right
if sorted(lst) == lst:
if max_size[0] < len(lst):
max_size[0] = len(lst)
max_node[0] = node
return lst
traverse(root)
return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root)) # Output: 4, 5, 6,
Đầu vào
root = TreeNode(12) ...
Đầu ra
4, 5, 6,