algorithm - BST :-Given the inorder successor of each node, 在 O(h) 中找到每个节点的父节点

Question

标题总结起来，我有一个包含节点的数组，它的顺序继承者我需要实现一个子程序来找到 O(h) 中任何给定节点的父节点

没有给出左右指针

Answer 1

我不确定我是否正确理解了您的问题，BST 中的有序后继仅表示下一个更高的元素。现在提供此信息，可以创建多个 BST。例如 [{1,4},{2,1},{3,2},{5,3}] 这里 {a,b} 表示 a 是节点，b 是有序的后继节点。所以树的一种可能实现是 4 IPO(读取是父级)1 和 NULL，1 IPO 2 和 NULL，2 IPO 3 和 NULL，最后 3 IPO 5 和 NULL。这些信息的复杂度为 O(n)，因为您只需遍历数组一次。