Lowest Common Ancestor Of Deepest Leaves: LCA Của Các Lá Sâu Nhất

Đề bài: Cho cây nhị phân, tìm LCA (Lowest Common Ancestor) của tất cả các leaf node có độ sâu lớn nhất.

Ví dụ: [1,2,3,4,5] → Tree: 1(root), left=2, right=3, 2.left=4, 2.right=5. Deepest leaves: 4,5 (depth 2). LCA = 2.

Ý tưởng: DFS Trả Về (depth, LCA)

Hàm đệ quy trả về tuple (max_depth_in_subtree, lca_of_deepest_leaves_in_subtree).

• Nếu node là leaf: (1, node).
• Đệ quy trái/phải → (d1, lca1), (d2, lca2).
• Nếu d1 > d2: deepest leaves chỉ ở trái → trả (d1+1, lca1).
• Nếu d2 > d1: deepest leaves chỉ ở phải → trả (d2+1, lca2).
• Nếu d1 == d2: deepest leaves ở cả 2 bên → node hiện tại là LCA → trả (d1+1, node).

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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return (0, None)
            if not node.left and not node.right:
                return (1, node)
            
            d1, lca1 = dfs(node.left)
            d2, lca2 = dfs(node.right)
            
            if d1 > d2:
                return (d1 + 1, lca1)
            elif d2 > d1:
                return (d2 + 1, lca2)
            else:
                return (d1 + 1, node)
        
        return dfs(root)[1]

# Helper: build tree from level-order list
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

# Test
root = build_tree([1,2,3,4,5])
ob = Solution()
lca = ob.lcaDeepestLeaves(root)
print(lca.val)  # 2

Phân tích

• Time: O(n) - duyệt mỗi node 1 lần.
• Space: O(h) recursion stack (h = height).
• 1 lần DFS duy nhất, không cần tìm depth max trước.

Kết luận

Đệ quy bottom-up trả về cả depth và LCA cùng lúc. Pattern này áp dụng cho nhiều bài LCA variant (deepest leaves, deepest nodes, etc.).