腾讯2018校园招聘在线笔试模拟考-编程题

发表于 | 分类于 ，

题目

描述

对于一颗满二叉排序树深度为 K,结点数为 2^K-1;节点值为 1 至 (2^K-1).
给出任意三个节点的值,输出包含该三个节点的最小子树的根节点值.

输入

输入包括一行,
第一个数为树的深读 K
后三个数为任意三个节点值

输出

输出包含一行,一个数字,为包含该三个节点的最小子树的根节点值

Example

Input

4 10 15 13

Output

12

题解

二分查找

  • 二分查找判断当前根节点值 root 与给定三节点中最大与最小值的关系
  • 若 root 大于最大值,说明三点在 root 左侧,root 赋值为左子树
  • 若 root 小于最小值,说明三点在 root 左侧,root 赋值为右子树
  • 若 root 大于等于最小值,小于等于最大值,root 即为所求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
using namespace std;

int main()
{
    int k,x[3],r,d;
    while(cin>>k>>x[0]>>x[1]>>x[2])
    {
        sort(x,x+3);
        r=1<<(k-1),d=k-2;
        while(!(r<=x[2]&&r>=x[0]))
        {
            if(r>x[2]) r-=(1<<d);
            else r+=(1<<d);
            --d;
        }
        cout<<r<<endl;
    }
}