首页 > 代码库 > 腾讯实习笔试编程题 满二叉搜索树求三个节点的最低公共祖先
腾讯实习笔试编程题 满二叉搜索树求三个节点的最低公共祖先
题目
对于一棵满二叉搜索树深度为K,节点数为2^k - 1,节点值为[1, 2^k - 1]。给出k和任意三个节点的值,输出包含该三个节点的最小子树的根节点值。
输入: 4 10 15 13
输出:12
思路
二分搜索,当搜索到节点x时,若x为三个节点之一或三个节点不在以x为根节点的树的子树的同一侧,则当前节点即为所求。否则二分
代码
1 import java.util.Scanner; 2 3 4 public class Main { 5 6 public static int binarySearch(int a,int b,int c, int left, int right) { 7 int m = left + (right - left) / 2; 8 9 if((a - m) * (b - m) <= 0 || (a - m) * (c - m) <= 0 || (c - m) * (b - m) <= 0) { 10 return m; 11 } else if(a > m) { 12 return binarySearch(a, b, c, m + 1, right); 13 } else { 14 return binarySearch(a, b, c, left, m - 1); 15 } 16 } 17 18 public static void main(String[] args) { 19 Scanner sc = new Scanner(System.in); 20 int k = sc.nextInt(); 21 int a = sc.nextInt(); 22 int b = sc.nextInt(); 23 int c = sc.nextInt(); 24 System.out.println(binarySearch(a, b, c, 1, (2 << k) - 1)); 25 } 26 }
腾讯实习笔试编程题 满二叉搜索树求三个节点的最低公共祖先
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。