public class GetBST {
public TreeNode root;
public GetBST(int data) {
root = new TreeNode(data);
}
public static void main(String[] args) {
/*创建根节点*/
GetBST getBST = new GetBST(3);
TreeNode x1 = new TreeNode(5);
getBST.initBst(x1);
/*创建众多子节点*/
TreeNode x2 = new TreeNode(4);
getBST.initBst(x2);
TreeNode x3 = new TreeNode(0);
getBST.initBst(x3);
TreeNode p = new TreeNode(-2);
getBST.initBst(p);
TreeNode q = new TreeNode(8);
getBST.initBst(q);
TreeNode result = lowestCommonAncestor(getBST.root, x2, q);
System.out.println(result.val);
}
/*插入搜索二叉树*/
public void initBst(TreeNode a){
TreeNode current;
current = root;
while (true) {
if (a.val >= current.val) {
if (current.right == null){
current.right = a;
return;
} else {
current = current.right;
}
} else {
if (current.left == null){
current.left = a;
return;
} else {
current = current.left;
}
}
}
}
/*搜索最小祖先*/
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
else if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
else
return root;
}
}
/*搜索二叉树结构*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
二叉搜索树的创建和判断最小祖先
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 题目 给一个排序数组(从小到大),将其转换为一棵高度最小的排序二叉树。 样例给出数组[1,2,3,4,5,6,7]...
- 《剑指offer》24题:Tips:如果面试题是要求处理一棵二叉树的遍历序列,我们可以先找到二叉树的根节点,再基于...