algorithm - BST中节点的Level Order Successor

Question

如果给定父指针(不使用 Queue )，我们如何在 bst 中找到节点的级别顺序后继？

Answer 1

在基本情况下，它是 node 的右兄弟节点。否则，您需要回绕到下一级，或者返回 No successor。

向上移动到有右 child 的下一个父节点，然后向左遍历它返回到 节点 的级别。如果您能够在没有右 child 的情况下回溯到 root，请从左侧向下到 level + 1。如果到达一个空的子 ptr，返回 no successor。

如果它不是完整的 BST，您可能需要做更多的工作 - 重复直到找到所需级别的节点。