狗家滇缅

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的特性，如果路径中有任何一个结点为空，就是不存在

byfwh 发表于 2018-12-10 04:53
不用O(n)啊 比如找6
6 -> 3 -> 1
然后

感谢，果然是没理解题目要考啥，现在明白了，谢谢回复！

hongchuj 发表于 2018-12-10 07:55
考虑到complete tree的特性，如果路径中有任何一个结点为空，就是不存在

也感谢楼主！