algorithm - 如何根据 BST 中的后继节点获取节点的父节点？

Question

在 BST 中，如果每个节点都没有指向其父节点的指针，则相反，有一个指向其后继节点的指针（也有左右子指针）。我们如何设计一种算法来根据后继指针获取其父代？

Answer 1

对于一个节点n，我们可以反复得到后继者s，直到我们得到一个那个s.left == n。s然后是父母。如果没有找到这样的节点，n是一个正确的孩子，我们重复获取后继者s，从第一个元素开始（通过重复调用很容易得到e = e.left）直到我们得到s.right == n，然后s是父节点。