[笔试编程]2017.8.29腾讯模拟，满二叉排序树找最小子树

题目

满二叉树排序树，高度k，节点数2^k-1，节点值1~2^k-1，给定3个数，求包含这3个数的最小子树的根节点。

输入4个数组，第一个值为高度，后面3个值为目标数。

例：
输入
4 10 15 13
输出
12

思路
分治
1. 判断中间数是否包含在要找的数里面，包含则中间数是所求
2. 判断目标数是否全在左/右半，是则继续找左/右半。
3. 不全在左/右半，则中间数为所求。

#include <iostream>
#include <algorithm>
#include <vector>
/*
满二叉排序数，层数k，节点数2^n-1, 1~2^n-1

4 10 15 13
*/

using namespace std;

int div(int left, int right, vector<int> &target)
{
int mid = (left + right) / 2;

if (find(target.begin(), target.end(), mid) != target.end()) {
return mid;
    }
else if (*(target.end() - 1) < mid) {
return div(left, mid - 1, target);
    }
else if (target[0] > mid) {
return div(mid + 1, right, target);
    }
else {
return mid;
    }
}

int main()
{
int k;
vector<int> target_nums(3);
cin >> k >> target_nums[0] >> target_nums[1] >> target_nums[2];

    sort(target_nums.begin(), target_nums.end());

int l = 1;
int r = powl(2,k) - 1;
int res = div(l, r, target_nums);

cout << res << endl;

return 0;
}