在BST中，如果每个节点都没有指向其父节点的指针，则指向其后继节点（也有左右子节点指针） . 我们如何设计一个算法来根据后继指针获取其父级？
对于节点 n ，我们可以重复获取后继 s ，直到得到一个 s.left == n . 然后 s 是父母 . 如果没有找到这样的节点， n 是一个正确的子节点，我们反复获取后继 s ，从第一个元素开始（通过重复调用 e = e.left 很容易获得）直到我们得到 s.right == n ，然后 s 是父节点 .
n
s
s.left == n
e = e.left
s.right == n
1 回答
对于节点
n，我们可以重复获取后继s，直到得到一个s.left == n. 然后s是父母 . 如果没有找到这样的节点，n是一个正确的子节点，我们反复获取后继s，从第一个元素开始（通过重复调用e = e.left很容易获得）直到我们得到s.right == n，然后s是父节点 .