问道面试题，关于bst的 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道面试题，关于bst的

问道面试题，关于bst的# JobHunting - 待字闺中

x*i2017-05-04 07:05

1 楼

给一列整数，比如［5 6 1 2 4 3］，和两个整数，
求的是，如果先把这一列整数构造成BST，那么所给的这两个整数的距离（就是从一
个点走到另一个点经过的边的数目）
比如，给的数是2，6，那么久返回3
我的做法很普通，就是一个一个整数的插入，生成bst, 然后求两个点的距离（可以先
求lowest ancestor)
但是结果11个test case只通过了8，不知道是什么test case
整数在0和2^31之间，整数的数量最多是2^31
请大侠直接，哪里可以优化
update:
谢谢大家回复
其实我的问题是，
有没有不explicitly构造bst也能求解的办法。如果input是2^31个integer的话，那
么我的bst就需要2^31 * 12(一个integer加上2个pointer）的memory, 这个大概是24g
，还是最保守的估算。是不是这样用的heap 内存太大，导致大的test case 不过？

b*62017-05-04 07:05

2 楼

After constructing the BST, you just need to find the common ancestor.
There is a similar problem on Leetcode

m*n2017-05-04 07:05

3 楼

你先搜到lowest common ancestor，然后从common ancestor开始再求距离试试？

s*n2017-05-04 07:05

4 楼

没考虑一个是另一个的祖先的情况吧

m*n2017-05-04 07:05

5 楼

共同先祖可以包括本身的。只要判断2个不同时大于或小于root就行。

【在 s*******n 的大作中提到】

: 没考虑一个是另一个的祖先的情况吧

x*i2017-05-04 07:05

6 楼

这些我都考虑到了

【在 m*******n 的大作中提到】

: 共同先祖可以包括本身的。只要判断2个不同时大于或小于root就行。

a*i2017-05-04 07:05

7 楼

有哪些test没过？

【在 x***i 的大作中提到】

: 这些我都考虑到了

x*i2017-05-04 07:05

8 楼

这个不知道，不给看

【在 a****i 的大作中提到】

: 有哪些test没过？

b*62017-05-04 07:05

9 楼

You probably do not need to construct the BST, and need to use property of
BST to figure out the result.
You know the root value and two points value, so you can traverse the array
from left to right to find the lowest ancestor without actually construct
BST.
To find the distance from ancestor to a node, you can also use the property
of BST.
So it can be an one pass in place solution.

n*x2017-05-04 07:05

10 楼

写了一下。不用build tree，找ancestor，求p和q到ancestor的距离即可，只是corner
case实在多，发现bug记得告诉我一声
int BST_distance(vector& nums, int p, int q){
if (p>q) return BST_distance(nums,q,p);
int ancestor=-1, grandpa=-1;
bool left;
for (int i=0; iif (nums[i]>=p && nums[i]<=q){
ancestor=i;
for (int j=i-1, dist=INT_MAX; j>=0; j--){
if (abs(nums[j]-nums[i])if (nums[j]>nums[i]) left=true;
else left=false;
grandpa = nums[j];
dist = abs(nums[j]-nums[i]);
}
}
break;
}
}
int distp=0, distq=0;
bool reach_p=false, reach_q=false, flag_p=false, flag_q=false;
int turn_p=0, turn_q=0, prev_p=nums[ancestor], prev_q=nums[ancestor];
for (int i=ancestor; iif (nums[i]<=nums[ancestor] && !reach_p){
if (!left && nums[i]continue;
if (!flag_p) {
if (nums[i]<=prev_p) {
distp++;
prev_p = nums[i];
}
if (nums[i]

turn_p=nums[i];
flag_p=true;
}
}
else {
if (nums[i]>turn_p && nums[i]<=p) distp++;
}
}
if (nums[i]>=nums[ancestor] && !reach_q){
if (left && nums[i]>grandpa && i!=ancestor && ancestor!=0)
continue;
if (!flag_q) {
if (nums[i]>=prev_q){
distq++;
prev_q = nums[i];
}
if (nums[i]>q) {
turn_q=nums[i];
flag_q=true;
}
}
else {
if (nums[i]=q) distq++;
}
}
if (nums[i]==p) reach_p=true;
if (nums[i]==q) reach_q=true;
if (reach_p && reach_q) break;
}
return distp+distq-2;
}