腾讯2017笔试——二叉排序树

题目

思路

• 对于二叉排序树的任何一个节点，其左子树的元素都小于右子树的元素
• 满二叉排序树树，树的结构可以确定

如果树的深度是$k$，满二叉树有$2^k-1$个元素，按从小到大的顺序排列为：$[a_1,a_2,…,a_{2^k-1}]$，则该满二叉树的结构如下：

1. 根节点的元素为$a_{\frac{2^k}{2}}$，$[a_1,a_2,…,a_{\frac{2^k}{2}-1}]$中的元素在根节点的左子树中，$[a_{\frac{2^k}{2}+1},…,a_{2^k-1}]$中的元素在根节点的右子树中
2. 对左子树、右子树两个区间再分别做1中的操作，得到最终的二叉排序树

给定三个节点，根据二叉排序树的性质，可以知道包含这三个节点的最小子树的根节点的值，一定在这三个节点值构成的区间$[min,max]$内

所以我们可以从上至下遍历二叉排序树

1. 如果根节点root值包含在三个节点值构成的最大区间内，则根节root点就是所求
2. 如果根节点值小于min，则令右子树的根节点为root
3. 如果根节点值大于min，则对左子树的根节点为root

重复上述操作，直到找到一个节点值为$t$，$t\in[min,max]$，该节点即为所求

代码

#include"stdafx.h"
#include<iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

FILE *fin;
int main()
{
    fin = fopen("in.txt", "r");
    int k ,a,b,c;
    int max, min;
    fscanf(fin,"%d", &k);
    fscanf(fin, "%d", &a);
    fscanf(fin, "%d", &b);
    fscanf(fin, "%d", &c);
    //求三个节点值最大的max和最小的min
    if (a > b&&a > c) {
        max = a;
        if (b > c) {
            min = c;
        }
        else
            min = b;
    }
    if (b > c&&b > a) {
        max = b;
        if (a > c) {
            min = c;
        }
        else
            min = a;
    }
    if (c > b&&c > a) {
        max = c;
        if (b > a) {
            min = a;
        }
        else
            min = b;
    }
    //搜索
    int low = 0;
    int high = pow(2, k);
    while (true) {
        int root = (low+high) / 2;
        if ((max - root)*(min - root) < 0){
            cout << root;
            break;
        }
        else{
            if (max < root) {
                high = root;
            }
            else {
                low = root;
            }
        }
    }
    
    system("pause");
    return 0;
}