Lowest Common Ancestor (LCA) ของ Binary Tree ใน Python

หา common ancestor ต่ำสุดของโหนด p และ q ใน binary tree

ตัวอย่าง

Tree:      3
         /   \
        5     1
       / \   / \
      6   2 0   8
         / \
        7   4

LCA(5, 1) = 3
LCA(5, 4) = 5

อัลกอริทึม Recursive

1. ถ้า root เป็น None หรือ root คือ p หรือ q → คืน root
2. หา LCA ใน left subtree และ right subtree
3. ถ้าทั้งสองข้างไม่เป็น None → root คือ LCA
4. มิฉะนั้น คืนข้างที่ไม่เป็น None

โค้ด

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

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        return left or right

# Helper สร้าง tree จาก list (level order)
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:
            left_idx = 2*i + 1
            right_idx = 2*i + 2
            if left_idx < len(nodes):
                node.left = nodes[left_idx]
            if right_idx < len(nodes):
                node.right = nodes[right_idx]
    return nodes[0]

# ทดสอบ
tree = build_tree([3,5,1,6,2,0,8,None,None,7,4])
sol = Solution()
p = tree.left        # 5
q = tree.right       # 1
print(sol.lowestCommonAncestor(tree, p, q).val)  # 3

สรุป

Recursive DFS สั้น กระชับ ใช้ได้กับ binary tree ทั่วไป (ไม่ใช่ BST)