腾讯4月3号笔试：完全二叉排序树

记不清题目了。依稀记得题目中说高度为k的完全二叉排序树的节点个数是2^k - 1。但是，完全二叉树可以不是满的啊？还是说这里要求此题中二叉树就得是满的。

当时在这个问题上纠结了很久，现在感觉很不必要。

然后，做法就是二分了。你们的做法呢？

后来写了下，如下：

int solve(vector<int> &vec, vector<int> &nums, int left, int right) {
    int index = (left+right)%2 == 0 ? (left+right)/2 : (left+right)/2+1;
    int root = vec[index];
    int res = 0;
    if (nums[2] < root) res = solve(vec, nums, left, index-1);
    else if (nums[0] > root) res = solve(vec, nums, index+1, right);
    else return root;
    return res;
}
int main()
{
    int k, a, b, c;    // 这里的k是k个节点了， 不是题目中的高度，反正思路是这样把。
    while (cin >> k >> a >> b >> c) {
        vector<int> vec(k, 0);
        for (int i = 0; i < k; i++) {
            vec[i] = i+1;
        }
        vector<int> nums{a, b, c};
        sort(nums.begin(), nums.end());
        cout << solve(vec, nums, 0, k-1) << endl;
    }
    return 0;
}

腾讯啊。#腾讯##C++工程师#

全部评论

推荐最新楼层

已删除

题目说了满

点赞回复分享

发布于 2017-04-04 16:58

村里滴、希望

吉林大学 C++

#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int res(int sum,int num1,int num2,int num3,int temp) { int min1 =min(num1,min(num2,num3)); int max2 =max(num1,max(num2,num3)); if(min1<=sum&&max2>=sum) { return sum; } else if(min1<sum&&max2<sum) { return res(sum-temp/2,num1,num2,num3,temp/2); } else return res(sum+temp/2,num1,num2,num3,temp/2); } int main() { int k,num1,num2,num3; cin>>k>>num1>>num2>>num3; int sum=1; for(int i=1;i<=k;i++) { sum=2*sum; } cout<<res(sum/2,num1,num2,num3,sum/2)<<endl; return 0; }

点赞回复分享

发布于 2017-08-29 22:10

Thare

淘天集团_技术专家

题目说的是满二叉树

点赞回复分享

发布于 2017-08-29 22:23

Thare

淘天集团_技术专家

import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int n = in.nextInt(); int[] nodes = new int[3]; for (int i = 0; i < n; ++i) { nodes[i] = in.nextInt(); } Arrays.sort(nodes); System.out.println(commonRoot(1 << (n - 1), nodes)); } } private static int commonRoot(int root, int[] nodes) { if (nodes[0] == root || nodes[2] == root) { return root; } if (nodes[0] > root) { return commonRoot(root + root >> 1, nodes); } if (nodes[2] < root) { return commonRoot(root >> 1, nodes); } else { return root; } } }

点赞回复分享

发布于 2017-08-29 22:42

有菠萝罐头吗

华中科技大学算法工程师

#include<iostream> using namespace std; int main() { int k, num1, num2, num3; cin>>k>>num1>>num2>>num3; int minNum = min(num1,(min(num2,num3))); int maxNum = max(num1,(max(num2,num3))); int flag1 = 1, flagMid = 1, flag2 = 1; while(k--) flag2 *= 2; flag2 = flag2 -1; flagMid = (flag1 + flag2)/2; while(minNum > flagMid || maxNum < flagMid) { if(minNum > flagMid) { flag1 = flagMid; flagMid = (flag1 + flag2 + 1)/2; } if(maxNum < flagMid) { flag2 = flagMid; flagMid = (flag1 + flag2)/2; } } cout<<flagMid<<endl; return 0; }

点赞回复分享

发布于 2017-08-30 00:00