题解 | #在二叉树中找到两个节点的最近公共祖先# 树形DP 模板

欢迎 Star：imhuay/studies

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        
        from dataclasses import dataclass
        
        @dataclass
        class Info:
            has_o1: bool  # 以当前结点为根节点的树中是否存在 o1
            has_o2: bool  # 以当前结点为根节点的树中是否存在 o2
            ret: int  # o1 和 o2 的最近公共祖先

        def dfs(x):
            if not x: return Info(False, False, None)
            
            l, r = dfs(x.left), dfs(x.right)
            has_o1 = l.has_o1 or r.has_o1 or x.val == o1
            has_o2 = l.has_o2 or r.has_o2 or x.val == o2
            ret = l.ret or r.ret or x.val if has_o1 and has_o2 else None
            return Info(has_o1, has_o2, ret)
        
        return dfs(root).ret