Lowest Common Ancestor of Deepest Leaves: LCA ของใบลึกสุด

โจทย์

กำหนด Binary Tree หา Lowest Common Ancestor (LCA) ของ ใบลึกสุด (deepest leaves) ทั้งหมด

• ใบ (leaf) = โหนดที่ไม่มีลูก
• ความลึก (depth): root=0, ลูกของ depth d = d+1
• LCA ของเซตโหนด = โหนดลึกที่สุดที่เป็น ancestor ของทุกโหนดในเซต

ตัวอย่าง: [1,2,3,4,5] → LCA ของใบลึกสุด (4,5) คือโหนด 2

    1
   / \
  2   3
 / \
4   5  ← ใบลึกสุด (depth 2)

อัลกอริทึม: Post-order DFS (Bottom-up)

ฟังก์ชัน dfs(node) คืนค่า (depth, lca_node):

• depth: ความลึกสูงสุดของใบใน subtree นี้
• lca_node: LCA ของใบลึกสุดใน subtree นี้

Logic: - ถ้า leaf: depth=1, lca=node - ถ้า left_depth > right_depth: ใบลึกอยู่ซ้าย → คืน (left_depth+1, left_lca) - ถ้า right_depth > left_depth: ใบลึกอยู่ขวา → คืน (right_depth+1, right_lca) - ถ้าเท่ากัน: ใบลึกอยู่ทั้งสองข้าง → node นี้คือ LCA → คืน (left_depth+1, node)

การติดตั้ง (Python Implementation)

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)
            
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            
            if left_depth > right_depth:
                return (left_depth + 1, left_lca)
            elif right_depth > left_depth:
                return (right_depth + 1, right_lca)
            else:
                return (left_depth + 1, node)
        
        return dfs(root)[1]

# Helper สร้าง tree
def build_tree(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i, node in enumerate(nodes):
        if node:
            li, ri = 2*i+1, 2*i+2
            if li < len(nodes):
                node.left = nodes[li]
            if ri < len(nodes):
                node.right = nodes[ri]
    return nodes[0]

# ทดสอบ
#     1
#    / \
#   2   3
#  / \
# 4   5
root = build_tree([1,2,3,4,5])
ob = Solution()
lca = ob.lcaDeepestLeaves(root)
print(lca.val)  # 2

# ทดสอบอีกตัว: ใบลึกอยู่คนละด้าน
#     1
#    / \
#   2   3
#  /   / \
# 4   5   6
#        /
#       7
root2 = build_tree([1,2,3,4,None,5,6,None,None,None,None,None,7])
lca2 = ob.lcaDeepestLeaves(root2)
print(lca2.val)  # 1 (root เป็น LCA ของ 4 และ 7)

Output

2
1

Complexity

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h) - recursion stack, h = ความสูงต้นไม้ (O(n) worst case)

สรุป

Post-order DFS คำนวณ depth และ LCA พร้อมกันในหนึ่งรอบ (single pass) เทคนิคนี้ใช้ได้กับโจทย์ LCA หลายรูปแบบ เช่น LCA of all nodes, LCA of deepest nodes, etc.

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ