狗家滇缅

今天 刚面完的 烙印 面的一般吧。

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

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

第一次发帖，求个赏呗，希望大家求职顺利~

byfwh 发表于 2018-12-10 04:07
哦哦 不好意思看错了
这题有个变种就是 树中节点可能为空 但编号还是按完全二叉树来的 不过做起来没区别

我其实还是没太get到这道题的考点，楼主描述说了不是算总节点数，要寻路，我没理解为什么不是算总节点数.....
如果像你说的变种，树中节点可能为空，但是按着complete tree来编号，就是要o(n)扫一遍了吧，lg(n)不知道怎么去除掉另外一半可能性，毕竟不是binary search tree那样的数字可以直接砍掉另一半，0(n)就更get不到考点了.....怀疑我完全理解错题目了。。。

fay19 发表于 2018-12-10 04:16
我其实还是没太get到这道题的考点，楼主描述说了不是算总节点数，要寻路，我没理解为什么不是算总节点数. ...

不用O(n)啊 比如找6
6 -> 3 -> 1
然后
1 -> 3 右走
3 -> 6 左走

从上往下遍历时只要发现空节点就没有 否则最后就能找到

fay19 发表于 2018-12-10 04:16
我其实还是没太get到这道题的考点，楼主描述说了不是算总节点数，要寻路，我没理解为什么不是算总节点数. ...

考虑到complete tree的特性，如果路径中有任何一个结点为空，就是不存在

哈哈哈哈请问楼主是不是东北人

补充内容 (2018-12-7 08:04):
该问的问题没问，如果找一个index根据大小找不就好了吗？是我理解错了么？

一路除以2取整数一直到1， 再反过来看这些值在不在树里？是不是我理解有问题？

gnoix 发表于 2018-12-7 08:03
哈哈哈哈请问楼主是不是东北人

补充内容 (2018-12-7 08:04):

= =不是东北人哦。。。嗯，是啊，就是怎么找路径的问题，我一开始想复杂了= =

这题好像看到过很多次..网站上有原题吗？

难道就是traversal，看看有没有index？

这是不是count number of nodes然后和k比较？

fay19 发表于 2018-12-9 00:34
这是不是count number of nodes然后和k比较？

应该不是 编号是按照完全二叉树来的 但是有可能有的编号那儿是空的

byfwh 发表于 2018-12-10 01:58
应该不是 编号是按照完全二叉树来的 但是有可能有的编号那儿是空的

楼主说是complete tree，应该不存在某个数对应的node是null的情况呀

fay19 发表于 2018-12-10 03:54
楼主说是complete tree，应该不存在某个数对应的node是null的情况呀

哦哦 不好意思看错了
这题有个变种就是 树中节点可能为空 但编号还是按完全二叉树来的 不过做起来没区别