我要招人

去企业版

首页 > 试题广场 >

二叉搜索树的最近公共祖先

[编程题]二叉搜索树的最近公共祖先

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。

4.p、q 为不同节点且均存在于给定的二叉搜索树中。

数据范围:

3<=节点总数<=10000

0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:

示例1

输入

{7,1,12,0,4,11,14,#,#,3,5},1,12

输出

说明

节点1 和 节点12的最近公共祖先是7

示例2

输入

{7,1,12,0,4,11,14,#,#,3,5},12,11

输出

说明

因为一个节点也可以是它自己的祖先.所以输出12

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

算法知识视频讲解

牛客题解官

发表于 2022-04-22 12:07:45

精华题解题目的主要信息：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先：对于该题的最近的公共祖先定义：对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大一个节点也可以是它自己的祖先二叉搜索树是若它的左子树不空，则左子树上展开全文

梦会绽放

发表于 2022-01-11 23:03:59

简单容易写思路：非递归，利用二叉搜索树的特点。左子树<根节点<右子树若p,q都比当前结点的值小，说明最近公共祖先结点在当前结点的左子树上，继续检查左子树；若p,q都比当前结点的值大，说明最近公共祖先结点在当前结点的右子树上，继续检查右子树；若p,q中一个比当前结点的值大，另一个展开全文

Black-K

发表于 2021-11-20 22:24:39

1.都在左边，或者都在右边，否则有一个就是我，，直接跳出，返回我； 2.递归调用 * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : va 展开全文

代码界的小白

发表于 2021-12-09 22:58:35

题目主要信息 1、给一颗二叉搜索树及两个节点 2、找到两个节点的最近公共祖先方法一:递归具体方法由于这是一棵二叉排序树，因此根节点的值大于左节点，小于右节点。如果需要找到最近公共祖先，那么这个祖先一定满足条件p<=root.val<=q 并且只存在三种情况如下图，可根据每种情况进展开全文

菜鸡孙连城

发表于 2022-03-19 23:32:06

递归 function lowestCommonAncestor( root , p , q ) { if(root==null) return null; // 如果两个值都小于根节点，说明祖先在左子树一侧 if(p<root.val && q&l 展开全文

牛客111587545号

发表于 2022-06-29 09:41:51

题目已经给出限制，两个子节点一定在树中，且val值唯一，因此只需要考虑以下四种情况 p，q都小于root 递归进入root->left p，q都大于root 递归进入root->left p或者q有一个等于root 直接返回此root->val p,q一个大于root，一个小于r 展开全文

牛客624491422号

发表于 2022-03-09 23:37:26

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿展开全文

呆喵挠琴

发表于 2021-12-08 13:07:04

题目的主要信息：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先. 二叉搜索树是若它的左子树不空，展开全文