2025/10/16
我的思路:从根节点 DFS,判断每个节点的子孙包含几个指定的节点,存起来,然后按BFS的顺序遍历,找第一个为2的
手写代码:
dict = {}
def DFS(T):
count = 0
if T.val == a or b:
count += 1
count += DFS(T.left)
count += DFS(T.right)
dict[T] = count
return count
def BFS(T):
stack = []
stack.push(T)
while stack != []:
t = stack.pop()
stack.push(t.left, t.right)
if dict[t] == 2:
return t
def Answer(T, a, b):
DFS(T)
return BFS(T)
答案:思路没问题,但是不够优雅
推荐答案:直接定义“公共祖先”函数DFS递归
2025/10/19
def isCommonAncester(t1, t2, t):
if isCommonAncester(t.left)