谷歌 店面面经

digdig 发表于 2019-10-10 04:54
这题应该还有附加条件的吧？比如这棵树从上至下从左往右都是递增的。如果符合这个条件倒是有log的解法，就 ...

如果已经找到了层数，可以详细说说怎么找到元素吗？因为我认为没法跳过之前层的元素直接找到这一层中的所有元素。。。
今天的米都加完了 明天给你加~谢谢！

Vyronas 发表于 2019-10-10 04:50
如果把当前层里的数存一个vector，就需要它上一层的所有node，上一层又需要上上一层。。。这样又相当于遍 ...

你可以看看李口222 complete tree, 用双层嵌套的binary search，时间复杂度是O(d^2)，d是node所在的层数。

a289206397 发表于 2019-10-10 04:46
这样确实是O(n)，刚刚想了一下。可以把

面试官让我优化成比O(n)小 我也很绝望啊。。。如果worst case还是O(n) 那求level似乎也没什么意义

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)

楼上各位是怎么做到在树的某一层做二分查找的？？？

digdig 发表于 2019-10-10 05:07
比如找99，已知在第4层

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

谢谢 像您说的找99在level4
我为什么从1开始直接走右边去8了呢？
为什么不是1->3->7->47这样先找，发现47比99小，然后再去7的右子49继续比较大小呢？

先找层L (0, 1, ...)，然后得到该层的元素个数M = 2^L，然后二分N并查询检验。
找层O(log N)，二分元素个数O(log M)，查询O(log N)，worst case O(log^2 N)。

Vyronas 发表于 2019-10-10 05:26
谢谢 像您说的找99在level4
我为什么从1开始直接走右边去8了呢？
为什么不是1->3->7->47这样先找，发现 ...

7的右子树还是比99小，这样就又要返回上层，就没法log n啦

从1去右边的8就是为了找到第4层的中点，联系一下二分查找来思考~

Vyronas 发表于 2019/10/10 04:02:56
那如果找到了对应的层数，我如何才能获得这一层中的所有数呢？还应该是用bfs吧？那不就还得是O(n)嘛？

假如有序的话，不用知道这一层所有节点啊。假如你知道了是第10层，这一层一共有512个点，你就用二分，首先mid＝256你就下到第10层从左到右数第256个点。然后看看是在左边还是右边，再继续二分找。  leetcode有一道题叫Count Complete Tree Nodes，solution里有一个类似的思路。

digdig 发表于 2019-10-10 05:40
7的右子树还是比99小，这样就又要返回上层，就没法log n啦

从1去右边的8就是为了找到第4层的中点，联 ...

有点明白了 谢谢你！明天给你加米！