谷歌 店面面经

感觉招到level也没啥用啊

chohan 发表于 2019-10-10 04:16
感觉招到level也没啥用啊

是啊我也这么觉得。。。面试官的提示让我很迷

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

直接找dfs 一直往左 和 一直往右 找出每一层数字的范围就是那个helperfunction了

abcisme 发表于 2019/10/10 04:22:56
直接找dfs 一直往左 和 一直往右 找出每一层数字的范围就是那个helperfunction了

只需要走最左边一遍就行了，不需要往右

abcisme 发表于 2019-10-10 04:22
直接找dfs 一直往左 和 一直往右 找出每一层数字的范围就是那个helperfunction了

已加米！找到层数后应该怎么做呢？想来想去还是O(n)。。。

我的想法是，如何能够确定要找的value一定存在。那么用vector<vector<TreeNode *>> level存每一层的TreeNode *。然后走一遍findlevel()找到level[i][0] <= target <= level[i].back()
然后再在这个level[i]里面做binarySearch。

a289206397 发表于 2019-10-10 04:36
我的想法是，如何能够确定要找的value一定存在。那么用vector level存每一层的TreeNode *。然后走一遍findl ...

谢谢你的回答 已加米！
不过在构建vector<vector<TreeNode *>>的时候是不是要走遍所有的node呀？如果是的话这一步就要O(n)了呀

Vyronas 发表于 2019-10-10 04:40
谢谢你的回答 已加米！
不过在构建vector的时候是不是要走遍所有的node呀？如果是的话这一步就要O(n)了 ...

这样确实是O(n)，刚刚想了一下。可以把<vector<vector<TreeNode *>>只存当层最左和最右这两个数（第一层除外）。这样依旧可以用findlevel()来找到合适层。找到以后再把当层里数存一个vector<TreeNode *>然后在binarySearch。这样应该就是log(n)
不过如果要找的那个数在最底层那还是O(n)，这个应该没办法

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

如果把当前层里的数存一个vector<TreeNode *>，就需要它上一层的所有node，上一层又需要上上一层。。。这样又相当于遍历所有node了呀

这题应该还有附加条件的吧？比如这棵树从上至下从左往右都是递增的。如果符合这个条件倒是有log的解法，就类似二分查找就行。先找层数，再找元素即可。