[编程题]在二叉树中找到两个节点的最近公共祖先
- 热度指数：1790 时间限制：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
备注:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public class Main {
private static HashMap<TreeNode,TreeNode> map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 构建二叉树
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
TreeNode root = new TreeNode(Integer.parseInt(params[1]));
HashMap<Integer, TreeNode> map = new HashMap<>();
map.put(root.val, root);
for(int i = 0; i < n; i++){
params = br.readLine().split(" ");
int val = Integer.parseInt(params[0]);
int leftVal = Integer.parseInt(params[1]);
int rightVal = Integer.parseInt(params[2]);
TreeNode node = map.get(val);
if(leftVal != 0) {
node.left = new TreeNode(leftVal);
map.put(leftVal, node.left);
}
if(rightVal != 0) {
node.right = new TreeNode(rightVal);
map.put(rightVal, node.right);
}
}
// 获得最近公共祖先
params = br.readLine().split(" ");
TreeNode p = map.get(Integer.parseInt(params[0])), q = map.get(Integer.parseInt(params[1]));
System.out.println(lowestCommonAncestor(root, p, q).val);
}
private static void setMap(TreeNode head) {
if(head==null)
return;
if(head.left!=null){
map.put(head.left,head);
}
if(head.right!=null)
{
map.put(head.right,head);
}
setMap(head.left);
setMap(head.right);
}
private static TreeNode lowestCommonAncestor(TreeNode head, TreeNode o1, TreeNode o2) {
if(head==null) return head;
map=new HashMap<TreeNode,TreeNode>();
if(head!=null) {
map.put(head,null);
}
setMap(head);
HashSet<TreeNode> path=new HashSet<>();
while(map.containsKey(o1)){
path.add(o1);
o1=map.get(o1);
}
while(!path.contains(o2)){
o2=map.get(o2);
}
return o2;
}
}
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public class Main {
private static HashMap<TreeNode,TreeNode> map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 构建二叉树
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
TreeNode root = new TreeNode(Integer.parseInt(params[1]));
HashMap<Integer, TreeNode> map = new HashMap<>();
map.put(root.val, root);
for(int i = 0; i < n; i++){
params = br.readLine().split(" ");
int val = Integer.parseInt(params[0]);
int leftVal = Integer.parseInt(params[1]);
int rightVal = Integer.parseInt(params[2]);
TreeNode node = map.get(val);
if(leftVal != 0) {
node.left = new TreeNode(leftVal);
map.put(leftVal, node.left);
}
if(rightVal != 0) {
node.right = new TreeNode(rightVal);
map.put(rightVal, node.right);
}
}
// 获得最近公共祖先
params = br.readLine().split(" ");
TreeNode p = map.get(Integer.parseInt(params[0])), q = map.get(Integer.parseInt(params[1]));
System.out.println(lowestCommonAncestor(root, p, q).val);
}
private static void setMap(TreeNode head) {
if(head==null)
return;
if(head.left!=null){
map.put(head.left,head);
}
if(head.right!=null)
{
map.put(head.right,head);
}
setMap(head.left);
setMap(head.right);
}
private static TreeNode lowestCommonAncestor(TreeNode head, TreeNode o1, TreeNode o2) {
if(head==null) return head;
map=new HashMap<TreeNode,TreeNode>();
if(head!=null) {
map.put(head,null);
}
setMap(head);
HashSet<TreeNode> path=new HashSet<>();
while(map.containsKey(o1)){
path.add(o1);
o1=map.get(o1);
}
while(!path.contains(o2)){
o2=map.get(o2);
}
return o2;
}
}
发表于 2022-04-15 18:55:48
回复(0)
可以用递归，但是我觉得那个思路有点难想，还是写了个用哈希表存储父节点的思路。首先遍历二叉树，构建好子节点指向父节点的映射，之后就可以像链表求交点一样求取最近公共祖先。先对p节点向上追溯到根，并记录下沿途的路径节点，之后q节点在往上追溯的过程中，碰到的第一个在路径节点集合中的节点就是我们要求的最近公共祖先节点。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 构建二叉树
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
TreeNode root = new TreeNode(Integer.parseInt(params[1]));
HashMap<Integer, TreeNode> map = new HashMap<>();
map.put(root.val, root);
for(int i = 0; i < n; i++){
params = br.readLine().split(" ");
int val = Integer.parseInt(params[0]);
int leftVal = Integer.parseInt(params[1]);
int rightVal = Integer.parseInt(params[2]);
TreeNode node = map.get(val);
if(leftVal != 0) {
node.left = new TreeNode(leftVal);
map.put(leftVal, node.left);
}
if(rightVal != 0) {
node.right = new TreeNode(rightVal);
map.put(rightVal, node.right);
}
}
// 获得最近公共祖先
params = br.readLine().split(" ");
TreeNode p = map.get(Integer.parseInt(params[0])), q = map.get(Integer.parseInt(params[1]));
System.out.println(lowestCommonAncestor(root, p, q).val);
}
private static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
HashMap<TreeNode, TreeNode> child2parent = new HashMap<>();
child2parent.put(root, root); // 根的父节点是自己
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node.left != null){
queue.offer(node.left);
child2parent.put(node.left, node);
}
if(node.right != null){
queue.offer(node.right);
child2parent.put(node.right, node);
}
}
if(child2parent.get(p) == child2parent.get(q)) return child2parent.get(p);
// 先记录p往上的路径
HashSet<TreeNode> memory = new HashSet<>();
memory.add(p);
while(child2parent.get(p) != p){
memory.add(child2parent.get(p));
p = child2parent.get(p);
}
// 然后再从q往上找最先与路径相交的节点
while(!memory.contains(q)) q = child2parent.get(q);
return q;
}
}
发表于 2021-11-14 20:05:55
回复(0)
import java.util.*;
public class Main {
static HashMap<Integer, Integer[]> hm;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] str = sc.nextLine().split(" ");
int n = Integer.parseInt(str[0]);
int r = Integer.parseInt(str[1]);
Integer[] child;
hm = new HashMap<>();
for(int i = 0;i < n;i++){
String[] str1 = sc.nextLine().split(" ");
int fa = Integer.parseInt(str1[0]);
int lc = Integer.parseInt(str1[1]);
int rc = Integer.parseInt(str1[2]);
child = new Integer[2];
child[0] = lc;
child[1] = rc;
hm.put(fa, child);
}
String[] str2 = sc.nextLine().split(" ");
int o1 = Integer.parseInt(str2[0]);
int o2 = Integer.parseInt(str2[1]);
Node root = new Node(r);
Node node1 = new Node(o1);
Node node2 = new Node(o2);
buildTree(root);
Node res = LCA(root, node1, node2);
System.out.println(res.val);
}
// 递归查找最近公共祖先
private static Node LCA(Node root, Node node1, Node node2){
if(root == null){
return null;
}
if(root.val == node1.val){
return node1;
}
if(root.val == node2.val){
return node2;
}
Node left = LCA(root.left, node1,node2);
Node right = LCA(root.right, node1,node2);
if(left != null && right != null){
return root;
}else if(left == null){
return right;
}else{
return left;
}
}
private static void buildTree(Node root) {
if(root == null)
return;
if(hm.containsKey(root.val)){
Node lc = null;
Node rc =null;
Integer[] ch = hm.get(root.val);
if(ch[0]!= 0){
lc = new Node(ch[0]);
lc.parent = root;
}
if(ch[1]!= 0){
rc = new Node(ch[1]);
rc.parent = root;
}
root.left = lc;
root.right = rc;
buildTree(lc);
buildTree(rc);
}
}
}
class Node {
int val;
Node parent;
Node left;
Node right;
public Node(int val){
this.val = val;
}
}
发表于 2019-09-19 16:14:28
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-04 01:25:04
-
2022-09-02 21:41:54 -
2022-08-30 16:39:39
-
2022-08-18 17:35:05 -
2022-07-26 13:58:59
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
