关注
import java.io.*;
import java.util.Scanner;
class BTNode{
public BTNode(int i, BTNode buildTree, BTNode buildTree2) {
this.data=i;
this.left=buildTree;
this.right=buildTree2;
}
int data;
BTNode left,right;
}
public class Main {
static BTNode lca(BTNode root,int l,int r) {
BTNode left=null;
BTNode right=null;
if(l<root.data&&r<root.data) {
left=lca(root.left,l,r);
}else if(l>root.data&&r>root.data) {
right=lca(root.right,l,r);
}else {
return root;
}
if(left==null)
return right;
else if(right==null)
return left;
return root;
}
static void Print(BTNode root,int data) {
if(root!=null) {
if(data==root.data)
f1=true;
Print(root.left,data);
Print(root.right,data);
}
}
static void Print2(BTNode root,int data) {
if(root!=null) {
if(data==root.data)
f2=true;
Print2(root.left,data);
Print2(root.right,data);
}
}
public static BTNode BuildTree(int[] treedata,int n){
if(treedata.length==0)
return null;
else{
if(n<treedata.length)
{
int l=n*2+1;
int r=n*2+2;
BTNode TreeRoot=new BTNode(treedata[n], BuildTree(treedata, l), BuildTree(treedata, r));
return TreeRoot;
}
else
return null;
}
}
static boolean f1=false;
static boolean f2=false;
public static void main(String args[]) throws Exception {
Scanner in=new Scanner(System.in);
String k=in.nextLine();
String tempdata=in.nextLine();
int l1=in.nextInt();
int r1=in.nextInt();
String[] data=tempdata.split(" ");
//System.out.println(l1+" "+r1);
BTNode treeroot;
int[] treedata=new int[data.length];
for(int i=0;i<treedata.length;i++)
{
treedata[i]=Integer.parseInt(data[i]);
//System.out.println(treedata[i]);
}
treeroot=BuildTree(treedata,0);
BTNode p = null,q=null;
p=treeroot;
q=treeroot;
Print(p,l1);
Print2(q,r1);
// System.out.println(f1);
// System.out.println(f2);
if(f1&&f2) {
BTNode res=lca(treeroot,l1,r1);
System.out.println(res.data);
}
else System.out.println(-1);
}
}//做的很挫,勉强能过
查看原帖
点赞 评论
相关推荐
04-14 12:56
东南大学 嵌入式软件开发 点赞 评论 收藏
分享
查看26道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 我的求职总结 #
479090次浏览 6781人参与
# 投格力的你,拿到offer了吗? #
187304次浏览 912人参与
# 27届实习投递记录 #
73301次浏览 815人参与
# 我是XXX,请攻击我最薄弱的地方 #
89641次浏览 617人参与
# 26届春招投递记录 #
11208次浏览 84人参与
# 产品面经 #
297268次浏览 2217人参与
# 海信求职进展汇总 #
105690次浏览 424人参与
# 中电科13所进度交流 #
6769次浏览 38人参与
# 拼多多工作体验 #
61332次浏览 431人参与
# 这些公司卡简历很严格 #
107127次浏览 484人参与
# AI让海力士市值突破9000亿美元 #
8855次浏览 111人参与
# 牛油的搬砖plog #
205649次浏览 1328人参与
# 风评不好的公司,你会去吗? #
155033次浏览 705人参与
# 哪一瞬间让你觉得“这班不如不上” #
46629次浏览 278人参与
# 入职第四天,心情怎么样 #
56332次浏览 474人参与
# 什么专业适合考公 #
72268次浏览 438人参与
# 小厂实习有必要去吗 #
94144次浏览 447人参与
# 我想象的工作vs实际工作 #
710191次浏览 5053人参与
# 得物app工作体验 #
67294次浏览 119人参与
# 正在实习的你,几点下班 #
353991次浏览 3067人参与
