我要招人

去企业版

首页 > 试题广场 >

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

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

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

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的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

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

数据结构和算法

发表于 2021-07-06 09:58:37

精华题解非递归写法要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下我们看到6和7公共祖先有5和展开全文

changed.

发表于 2021-07-16 21:15:35

精华题解首先要明确题意，既寻找给定非空二叉树中的两个节点的最近公共祖先节点祖先：若节点 o1 在 root的左子树/右子树上，或 o1 = root，则 root 为 o1 祖先最近公共祖先：节点 root 为 o1 和 o2 的公共祖先，且 root的左子树/右子树都不为 o1 和 o2的公共展开全文

牛客题解官

发表于 2022-04-22 12:09:55

精华题解题目的主要信息：给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点二叉树非空，且每个节点值均不同举一反三：学习完本题的思路你可以解决如下题目： BM29. 二叉树中和为某一值的路径（一） BM37. 二叉搜索树的最近公共祖先方展开全文

棒棒糖🍭201906101800876

发表于 2021-07-20 10:48:16

精华题解 nc102 在二叉树中找到两个节点的最近公共祖先 1. 递归搜索设问题为LCA(root, o1, o2), 该问题有以下递归性质：如果o1和o2都在root的左子树中，那么LCA(root, o1, o2) = LCA(root->left, o1, o2). 如果o1和o2都在roo 展开全文

码农10086号

发表于 2020-11-21 17:27:04

非原创，百度总结：此方法重点在于子节点路径的查找上，判断某个节点在不在从根节点到子节点的路径上的思路很简单：如果某个节点恰好是子节点或者他的左子树包含待查找的子节点或者他的右子树包含待查找节点，那么就可以判定当前节点位于子节点的路径上，那么就把他入栈保存起来，那么出栈顺序就是从根节点到子节点的路径。展开全文

悟空WK

发表于 2020-11-25 14:33:16

牛客题霸NC102在二叉树中找到两个节点的最近公共祖先Java题解https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&&tqId=35027&rp=1&ru=/ta/j 展开全文

小陆要懂云

发表于 2021-06-23 14:31:10

int lowestCommonAncestor(TreeNode* root, int o1, int o2) { return helper(root,o1,o2)->val; } TreeNode* helper(TreeNode* root, int o1, int o2) 展开全文

Fadeways

发表于 2021-09-27 15:38:44

/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * * @param root TreeNode类 * @param o 展开全文

Maokt

发表于 2021-07-19 18:08:29

算法思想一：递归解题思路：若 root 是 o1,o2 的最近公共祖先，则只可能为以下情况之一： o1 和 o2 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）； o1 = root ，且 o1 在 root 的左或右子树中；展开全文

白衣少年201908292030397

发表于 2021-09-17 09:32:48

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Sol 展开全文

加油做题

发表于 2022-05-28 15:24:44

step 1：如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。 step 2：如果都不匹配，则分别递归左、右子树。 step 3：如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先. step 4：如果两个节点都出现在左子树，则说明最展开全文

人定胜天~

发表于 2021-01-06 21:02:06

若root是p,q的最近公共祖先,则只可能为以下情况之一： p和q在root的子树中，且分列root的异侧（即分别在左、右子树中）； p=root,且q在root的左或右子树中； q=root，且p在root的左或右子树中；/** * struct TreeNode { * int val; 展开全文