Cho gốc cây nhị phân, xóa tất cả nút chỉ có 1 con (bypass nút đó, nối cha trực tiếp với con).
Ví dụ: Cây gốc có nút 2 (chỉ có con trái 4), nút 4 (chỉ có con phải 6) → sau khi xóa: 1 nối thẳng đến 6.
Giải pháp: Đệ quy post-order. Nếu nút lá → giữ. Nếu chỉ có 1 con → trả về kết quả đệ quy của con đó (bypass). Nếu có 2 con → đệ quy cả 2, gán lại, trả về gốc.
Ví dụ triển khai
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
if root:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root):
if not root:
return root
if not root.left and not root.right:
return root
if not root.left:
return self.solve(root.right)
if not root.right:
return self.solve(root.left)
root.left = self.solve(root.left)
root.right = self.solve(root.right)
return root
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)
res = ob.solve(root)
print_tree(res) # 6, 1, 7, 5, 8,
Đầu vào
Tree: 1(2(4(,6)), 3(5(7,8)))
Đầu ra
6, 1, 7, 5, 8,