新鲜狗家实习背靠背

95345324523578346394oierwe

笨笨李 发表于 2020/01/14 08:08:40
95345324523578346394oierwe

说啥呢 没看懂

WarriorZ 发表于 2020/01/11 08:11:08
第一题最优应该能到O(height)，但是需要输入的是bst。只是binary tree的话怎么说都要O(n)吧？

每次都计算出根节点的索引，然后判断向左查找还是向右查找。

O(tree height) aka O(log tree nodes)

在root根据index以及左子树有多少节点
判断向左走还是向右走
如果向右走，调整index大小
重复直到当前节点就是想要的结果