首页 > 试题广场 >

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

[编程题]在二叉树中找到两个节点的最近公共祖先
  • 热度指数：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

输入

8 1
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0
7 8 0
8 0 0
4 5

输出

2

备注:


算法知识视频讲解
开通博客
头像 我要出去乱说
发表于 2022-07-01 09:40:48
1、思路 对二叉树进行前序遍历，找到目标节点后就返回该节点； 每次递归分三种情况讨论： 1、若当前节点的左右子树返回值都不为空，则当前节点即是最近公共祖先； 2、若只有左子树返回值不为空，说明其中一个节点或者两个节点都在左子树，直接返回左子树的返回值； 3、若只有右子树返回值不为空， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 小YuHao
发表于 2022-05-16 23:31:44
import java.util.*; import java.io.*; class TreeNode {     public int value;     public TreeNode left;     public TreeNo 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 WYJ96
发表于 2021-07-27 05:31:13
import java.io.*; import java.util.*; public class Main { static class Node{ int value; Node left; Node right; p 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 小强强_
发表于 2020-03-29 23:18:56
整个题目其实只需要写出lca函数就OK了，但是前面根据输入构建树等一系列操作，还是挺恶心的，写得挺累，但是感觉没什么意义。 import java.util.*; public class Main { private static TreeNode p = null; priva 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 秋風掃落葉
发表于 2019-09-19 16:26:26
import java.util.*; public class Main { static HashMap hm; public static void main(String[] args) { Scanner sc = new Scanner(System.in 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树 高级结构
上传者：小小
难度：
16条回答 6980浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号