首页 > 试题广场 >

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

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

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 $1 \le n \le 10^5 \$ , 节点值val满足区间 [0,n)

要求：时间复杂度 $O(n)$

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

示例1

输入

{3,5,1,6,2,0,8,#,#,7,4},5,1

示例2

{3,5,1,6,2,0,8,#,#,7,4},2,7

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

树

难度：

0条回答 2226收藏 9868浏览

查看代码

扫一扫，把题目装进口袋