题解 | #在二叉树中找到两个节点的最近公共祖先# 不用注释也能看懂的递归代码
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
class Solution:
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
from dataclasses import dataclass
@dataclass
class Info: # 期望从子节点中获取的信息
has_o1: bool
has_o2: bool
ret: int
def dfs(x):
if not x: return Info(False, False, -1)
l, r = dfs(x.left), dfs(x.right)
has_o1 = x.val == o1 or l.has_o1 or r.has_o1
has_o2 = x.val == o2 or l.has_o2 or r.has_o2
ret = -1
if x.val == o1 and has_o2:
ret = x.val
elif x.val == o2 and has_o1:
ret = x.val
elif has_o1 and has_o2:
ret = l.ret if l.ret != -1 else r.ret
ret = x.val if ret == -1 else ret
return Info(has_o1, has_o2, ret)
return dfs(root).ret
