在二叉树中找到两个节点的最近公共祖先

[编程题]在二叉树中找到两个节点的最近公共祖先

热度指数：1793 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

最后一行为节点 o1 和 o2。

输出描述:

输出一个整数表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

Python3

毓毓子最可爱

#节点数，根节点
n,root=map(int,input().split())
#树和C1的祖先数组
f,v=[0]*(n+1),[1]*(n+1)
#建立树
for _ in range(n):
    fa,lch,rch=map(int,input().split())
    f[lch]=f[rch]=fa
c1,c2=map(int,input().split())
#寻找c1的所有祖先
while c1!=root:
    v[c1],c1=0,f[c1]
#第一个没被标记的祖先就是最近公共祖先
while c2!=root and v[c2]:
    c2=f[c2]
print(c2)

发表于 2021-08-06 09:04:36 回复(0)