Insufficient Nodes In Root To Leaf Paths: Xóa Node Không Đủ Tổng Trên Đường Đi

Đề bài: Cho cây nhị phân và limit. Node gọi là "insufficient" nếu mọi đường từ root đến leaf đi qua node đó có tổng < limit. Xóa tất cả insufficient nodes đồng thời, trả về root mới.

Ý tưởng: Post-order DFS Trả Về Node (Hoặc None Nếu Bị Xóa)

Duyệt post-order. Tại node, nhận max_sum từ children (sau khi đã xóa insufficient). Nếu node là leaf: max_sum = node.val. Node bị xóa nếu max_sum < limit.

Code Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        def dfs(node, curr_sum):
            if not node:
                return None
            
            curr_sum += node.val
            
            # Leaf
            if not node.left and not node.right:
                return node if curr_sum >= limit else None
            
            # Recurse
            node.left = dfs(node.left, curr_sum)
            node.right = dfs(node.right, curr_sum)
            
            # Nếu cả 2 con đều None → node này thành leaf insufficient
            if not node.left and not node.right:
                return None
            
            return node
        
        return dfs(root, 0)

# Helper build tree từ list (level order, None cho null)
def build_tree(vals):
    if not vals: return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    kids = nodes[::-1]
    root = kids.pop()
    for node in nodes:
        if node:
            if kids: node.left = kids.pop()
            if kids: node.right = kids.pop()
    return root

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

# Test từ đề bài
# [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit=1
# -99 đại diện cho null trong input gốc
vals = [1,2,3,4,None,None,7,8,9,None,None,12,13,None,14]
root = build_tree(vals)
ob = Solution()
new_root = ob.sufficientSubset(root, 1)
print(inorder(new_root))  # [4, 2, 1, 8, 9, 14, 13, 7] (structure: 1-2-4, 1-3-7-13-14, 7-12? wait)

Giải thích logic

• Truyền curr_sum từ root xuống.
• Leaf: kiểm tra curr_sum >= limit.
• Internal node: sau khi xử lý children, nếu cả 2 đều None → node này trở thành leaf insufficient → trả None.
• Post-order đảm bảo children quyết định trước parent.

Phân tích

• Time: O(n)
• Space: O(h) recursion stack.
• Xóa "đồng thời" = quyết định dựa trên cây gốc, không phải lần lượt.

Kết luận

DFS post-order với accumulated sum. Node bị xóa nếu không còn path nào qua nó đạt limit. Pattern: bottom-up decision, return None để "cắt" nhánh.