求二叉树节点有序秩的有效算法

Question

给定二叉树(不一定是二叉树搜索树)和该树中的一个节点，有什么有效的算法(最好用Java语言)来查找该节点的有序秩？

通过遍历(递归或迭代)，O(n)算法是可能的。还有更好的吗？谢谢你的建议。

Answer 1

想象一下最坏的情况:每个节点只有一个剩下的子节点，所以整个树就变成了一个链表。

如果给定一个根，要计算排名，您需要访问叶，在这种情况下，这需要花费O(n)。因此，在最坏的情况下，O(n)是您可以实现的最佳目标，而无需在节点中存储其他信息。