谷歌 店面面经

面试官口音很标准，上来就开始做题：
给一个perfect tree（如图），写一个函数：已知某个node的value，返回该node的指针。
一

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

容 (2019-10-10 04:34):
每个回复我都会加米！谢谢各位帮忙

把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O(n/2), 便宜了一点点

Vyronas 发表于 2019-10-10 04:56
如果已经找到了层数，可以详细说说怎么找到元素吗？因为我认为没法跳过之前层的元素直接找到这一层中的所 ...

比如找99，已知在第4层

那么从1开始，找右子树的第4层最小值（从右孩子还是一直往左走2层）80，99>80，1走右孩子到4.
在从4找找右子树的第4层最小值（从右孩子还是一直往左走1层）120，99<120，从4走到12

这样时间是O(d^2), d=O(log n)

machdebagua 发表于 2019-10-10 03:35
把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O ...

worst case还是O n

machdebagua 发表于 2019-10-10 03:35
把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O ...

可是如果还是要从root出发 worst case 应该还是O(n)呀？

这个tree还有什么特点吗？看你发的图，每层都是递增的，以及是不是balanced tree?

看例子是按level从上到下，从左到右排好序的perfect tree？ 如果是这样的话，可以一直走右节点，直到当前节点比自己大，那就找到层数。然后在某一层用二分查找。

MiniMinyi 发表于 2019-10-10 03:58
看例子是按level从上到下，从左到右排好序的perfect tree？ 如果是这样的话，可以一直走右节点，直到当前节 ...

那如果找到了对应的层数，我如何才能获得这一层中的所有数呢？还应该是用bfs吧？那不就还得是O(n)嘛？

hqOffer 发表于 2019-10-10 03:57
这个tree还有什么特点吗？看你发的图，每层都是递增的，以及是不是balanced tree?

这个tree是balance的 每层递增 而且所有的leaf node都是同层

Vyronas 发表于 2019/10/10 04:04:36
这个tree是balance的 每层递增 而且所有的leaf node都是同层

那这样的话可以用DFS pre order traversal 来确定value所在的层数，空间没要求的话可以直接DFS来把level order traversal存下来，这样时间是logn。好一点的话只需要走最左边的一条path就能确定所找的那个值的level了，应该就是面试官所说的helper function 。求加米(￣▽￣)

hqOffer 发表于 2019-10-10 04:11
那这样的话可以用DFS pre order traversal 来确定value所在的层数，空间没要求的话可以直接DFS来把level o ...

感谢回答！但是我还是有个问题。。你说把level order traversal存起来，这难道不需要遍历我要找的某个level以及它之前level的所有node嘛？这样为什么会是logn呀？