腾讯今晚的满二叉树是啥意思，为啥样例最后输出是12。

不知有没有特殊情况没考虑到

public static int get(int h, int a, int b, int c) { int init = (int) Math.pow(2, h - 1); int val = init / 2; while (true) { if (init > a && init > b && init > c) init -= val; else if (init < a && init < b && init < c) init += val; else return init; val /= 2; } }

#include<bits/stdc++.h> using namespace std; typedef vector<int>::iterator vii; int father(int k, int n) { if (n > k) abort(); int low = 1, high = k; int mid, last = (low + high) / 2; while (low <= high) { mid = (low + high) / 2; if (mid == n) return last; if (n < mid) high = mid - 1; else low = mid + 1; last = mid; } } int com_father(int k, int m, int n) { vector<int> fm, fn; while (m != ((k+1) >> 1)) { fm.insert(fm.begin(), m); m = father(k, m); } fm.insert(fm.begin(), m); while (n != ((k + 1) >> 1)) { fn.insert(fn.begin(), n); n = father(k, n); } fn.insert(fn.begin(), n); int i; for (i = 0; i < fm.size() && i < fn.size(); i++) { if (fn[i] != fm[i]) break; } return fm[i-1]; } int main() { while (true) { int k, n1, n2, n3; cin >> k >> n1 >> n2 >> n3; k = (2 << k) - 1; n1 = com_father(k, n1, n2); n2 = com_father(k, n1, n3); cout << n2 << endl; } return 0; }

#include <stdio.h> #include <iostream> using namespace std; /*         8       /      \      /        \     4          12    / \            /  \   2   6      10   14  / \     / \    / \     /  \ 1  3 5  7 9 11 13 15            */ int zhongjianzhi(int m ,int n,int curroot,int k){   if(curroot == (m + n)/ 2)  return curroot;   if(m > curroot && n < curroot) return curroot;   else if (m> curroot && n > curroot){     curroot = (curroot + (1<<k)) /2;     zhongjianzhi(m,n,curroot,k);   }   else {     curroot = (curroot + 0)/2;     zhongjianzhi(m,n,curroot,k);   } } int main(){   int k,a,b,c;   cin >> k;   cin >>  a >>  b >>  c;    int num = 0;    int maxx = max(max(a,b),c);    int minn = min(min(a,b),c);    int curroot = 1<<(k-1);    num = zhongjianzhi(maxx,minn,curroot,k);    cout << num << endl;    return 0; }

不是说了满二叉排序树吗，对于给定深度，树就确定了

package xiaozhao2017; import java.util.Scanner; public class FullBST { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int k=scan.nextInt(); int num1=scan.nextInt(); int num2=scan.nextInt(); int num3=scan.nextInt(); String s1=convertNumberToKLength(k,num1); String s2=convertNumberToKLength(k,num2); String s3=convertNumberToKLength(k,num3); System.out.println(minRootNumber(s1,s2,s3)); } public static int minRootNumber(String s1,String s2,String s3){ int difference=0; for(int i=0;i<s1.length();i++){ if(!((s1.charAt(i)==s2.charAt(i))&&((s2.charAt(i)==s3.charAt(i))))){ difference=i; break; } } String ans=s1.substring(0,difference); ans+="1"; for(int i=0;i<=s1.length()-ans.length();i++){ ans+="0"; } return convertBinaryToDecimal(ans); } public static int convertBinaryToDecimal(String str){ int ans=0; for(int i=str.length()-1;i>=0;i--){ int bit=Integer.parseInt(str.charAt(i)+""); if((bit&1)!=0){ ans+=Math.pow(2, str.length()-i-1); } } return ans; } public static String convertNumberToKLength(int k,int n){ String str=Integer.toBinaryString(n); String s=""; if(str.length()<k){ for(int i=0;i<k-str.length();i++){ s+="0"; } s+=str; return s; } return str; } }

不大记得题了，没来得及做，这题是不是就是求若干节点的最小公共祖先，还是在一颗满二叉排序树上？

它是排序树，而且是满的。觉得是1的同学看看上面画了树的图，根是8的那张。满的二叉排序树只能那么画，看了图就知道了，答案只需要算一算就得出来了

表示考试期间一直在划满二叉树 考完后才反应过来树怎么画

理解错了，看题目好久，考完做了下 #include<iostream> #include<map> #include<vector> #include<algorithm> using namespace std; int data[10000]; void buildtree(int n) { int zhi = n - 1; int index = 1; for (int i = 0; i < zhi; i++) { index = index * 2; } int end = index * 2 - 1; for (int i = index; i <= end; i++) { data[i] = 2 * (i - index) + 1; } for (int i = index - 1; i >= 1; i--) data[i] = (data[i * 2] + data[i * 2 + 1]) / 2;   } void findroot(int m, int p, int q) { int index1 = 0; int index2 = 0; int index3 = 0; for (int i = 1; i < 10000; i++) { if (data[i] == m) index1 = i; if (data[i] == p) index2 = i; if (data[i] == q) index3 = i; } while (index1 != index2) { if (index1 > index2) index1 = index1/ 2; else if (index2 > index1) index2 = index2 / 2; }   while (index3 != index2) { if (index3 > index2) index3= index3 / 2; else if (index2 > index3) index2 = index2 / 2; }   cout << data[index3]<< endl; } int main() { int n, m, p, q; while (cin >> n >> m >> p >> q) { buildtree(n); findroot(m, p, q); } }

原来二叉排序树是 Binary search Tree。整个过程都在搞翻译，什么是hash桶，原来是Hash bucket

二叉排序树就是12啊，楼上都怎么审题的

二叉排序树。以4为例，根节点为8，把树画出来就看的出来了

            8      4           12   2    5   10     13 1 3 6 7 9 11 14 15 是12吧

题目写了二叉排序树，我瞎了……审题都审错了

我也觉得是1，我在监控下面爆粗了，不会被听到吧

我理解的第一题是求三个节点的最近公共祖先，我的代码样例输出是1，不懂12是什么意思，实在搞不懂正确题意是什么 逆序数那个我是DP的dp[i][3]表示第i个字符前字符j出现的次数然后扫一遍更新

一开始我也觉得好奇怪，但是再看清楚一点，发现是最小子树的根

不知道是没读懂意思还是样例错误，不知道为啥输出12。也不多来几组样例，腾讯也真是为我们节约流量。