二叉搜索树（BST）是一种帮助我们有效解决现实世界问题的数据结构。
什么是二叉搜索树？
BST 是一棵树，其中每个节点最多指向两个节点，通常称为左子节点和右子节点。此外，每个节点的值都大于左子节点且小于右子节点。
例如，让我们想象三个节点：A=2、B=1 和 C=4。因此，一种可能的 BST 将 A 作为根，B 作为其左子节点，C 作为其右子节点。
1、递归解决方案
直接解决方案是使用递归遍历树并提前返回其任何子节点等于目标值的节点。
我们首先在 TreeNode类中定义一个公共方法：
TreeNode parent(int target) throws NoSuchElementException {
return parent(this, new TreeNode(target));
}
|
现在，让我们在TreeNode类中定义Parent()方法的递归版本：TreeNode parent(TreeNode current, TreeNode target) throws NoSuchElementException {
if (target.equals(current) || current == null) {
throw new NoSuchElementException(format("No parent node found for 'target.value=%s' " +
"The target is not in the tree or the target is the topmost root node.",
target.value));
}
if (target.equals(current.left) || target.equals(current.right)) {
return current;
}
return parent(target.value < current.value ? current.left : current.right, target);
}
|
该算法首先检查当前节点是否是最顶层的根节点或者该节点是否不存在于树中。在这两种情况下，节点都没有父节点，因此我们抛出NoSuchElementException。然后，算法检查当前节点子节点是否等于目标节点。如果是，则当前节点是目标节点的父节点。因此，我们返回current。
最后，我们根据目标值使用递归调用向左或向右遍历 BST 。
让我们测试一下我们的递归解决方案：
@Test
void givenBinaryTree_whenFindParentNode_thenReturnCorrectParentNode() {
assertThrows(NoSuchElementException.class, () -> subject.parent(1231));
assertThrows(NoSuchElementException.class, () -> subject.parent(8));
assertEquals(8, subject.parent(5).value);
assertEquals(5, subject.parent(3).value);
assertEquals(5, subject.parent(7).value);
assertEquals(3, subject.parent(4).value);
// assertions for other nodes
}
|
在最坏的情况下，算法最多执行n次递归操作，每次查找父节点的成本 为O(1) ，其中n是 BST 中的节点数。因此，时间复杂度为O (n) 。在平衡良好的 BST中，该时间降至 O(log n)，因为其高度始终最多为log n。此外，该算法使用堆空间进行递归调用。因此，在最坏的情况下，当我们找到叶节点时，递归调用就会停止。因此，该算法最多堆叠h次递归调用，这使得其 空间复杂度为O(h)，其中 h是 BST 的高度。
2、迭代解决方案
几乎任何递归解决方案都有迭代版本。特别是，我们还可以使用堆栈和while循环而不是递归来找到 BST 的父级。
为此，我们将 iterativeParent()方法添加到TreeNode类：
TreeNode iterativeParent(int target) {
return iterativeParent(this, new TreeNode(target));
}
|
上面的方法只是下面辅助方法的接口：TreeNode iterativeParent(TreeNode current, TreeNode target) {
Deque <TreeNode> parentCandidates = new LinkedList<>();
String notFoundMessage = format("No parent node found for 'target.value=%s' " +
"The target is not in the tree or the target is the topmost root node.",
target.value);
if (target.equals(current)) {
throw new NoSuchElementException(notFoundMessage);
}
while (current != null || !parentCandidates.isEmpty()) {
while (current != null) {
parentCandidates.addFirst(current);
current = current.left;
}
current = parentCandidates.pollFirst();
if (target.equals(current.left) || target.equals(current.right)) {
return current;
}
current = current.right;
}
throw new NoSuchElementException(notFoundMessage);
}
|
该算法首先初始化一个堆栈来存储父候选。那么主要取决于四个主要部分：
- 外部while循环检查我们是否正在访问非叶节点或者父候选堆栈是否不为空。在这两种情况下，我们都应该继续遍历 BST，直到找到目标父代。
- 内部 while循环再次检查我们是否正在访问非叶节点。此时，访问非叶节点意味着我们应该首先向左遍历，因为我们使用中序遍历。因此，我们将父候选添加到堆栈中并继续向左遍历。
- 访问左侧节点后，我们从 Deque 中轮询一个节点，检查该节点是否是目标的父节点，如果是则返回。如果找不到父母，我们就会继续向右移动。
- 最后，如果主循环完成而没有返回任何节点，我们可以假设该节点不存在或者它是最顶层的根节点。
现在，让我们测试一下迭代方法：@Test
void givenBinaryTree_whenFindParentNodeIteratively_thenReturnCorrectParentNode() {
assertThrows(NoSuchElementException.class, () -> subject.iterativeParent(1231));
assertThrows(NoSuchElementException.class, () -> subject.iterativeParent(8));
assertEquals(8, subject.iterativeParent(5).value);
assertEquals(5, subject.iterativeParent(3).value);
assertEquals(5, subject.iterativeParent(7).value);
assertEquals(3, subject.iterativeParent(4).value);
// assertion for other nodes
}
|
在最坏的情况下，我们需要遍历整棵o树来找到父节点，这使得迭代解的空间复杂度为O(n)。同样，如果 BST 是很好平衡的，我们可以在O(log n)中做同样的事情。当我们到达叶节点时，我们开始从ParentCandidates堆栈中轮询元素。因此，用于存储父候选的附加堆栈最多包含h 个元素，其中 h是 BST 的高度。因此，它也具有O(h)的 空间复杂度。
3、使用父指针创建 BST
该问题的另一个解决方案是修改现有的 BST 数据结构来存储每个节点的父节点。
为此，我们创建另一个名为ParentKeeperTreeNode的类，其中包含一个名为Parent的新字段：
class ParentKeeperTreeNode {
int value;
ParentKeeperTreeNode parent;
ParentKeeperTreeNode left;
ParentKeeperTreeNode right;
// value field arg constructor
// equals and hashcode
}
|
现在，我们需要创建一个自定义insert()方法来保存父节点：void insert(ParentKeeperTreeNode currentNode, final int value) {
if (currentNode.left == null && value < currentNode.value) {
currentNode.left = new ParentKeeperTreeNode(value);
currentNode.left.parent = currentNode;
return;
}
if (currentNode.right == null && value > currentNode.value) {
currentNode.right = new ParentKeeperTreeNode(value);
currentNode.right.parent = currentNode;
return;
}
if (value > currentNode.value) {
insert(currentNode.right, value);
}
if (value < currentNode.value) {
insert(currentNode.left, value);
}
}
|
当为当前节点创建新的左或右子节点时，insert() 方法还会保存父节点。在这种情况下，由于我们正在创建一个新的子节点，因此父节点始终是我们正在访问的当前节点。最后，我们可以测试存储父指针的 BST 版本：
@Test
void givenParentKeeperBinaryTree_whenGetParent_thenReturnCorrectParent() {
ParentKeeperTreeNode subject = new ParentKeeperTreeNode(8);
subject.insert(5);
subject.insert(12);
subject.insert(3);
subject.insert(7);
subject.insert(1);
subject.insert(4);
subject.insert(11);
subject.insert(14);
subject.insert(13);
subject.insert(16);
assertNull(subject.parent);
assertEquals(8, subject.left.parent.value);
assertEquals(8, subject.right.parent.value);
assertEquals(5, subject.left.left.parent.value);
assertEquals(5, subject.left.right.parent.value);
// tests for other nodes
}
|
在这种类型的 BST 中，我们在节点插入期间计算父节点。因此，为了验证结果，我们可以简单地检查每个节点中的父引用。因此，我们可以在O(1)时间内通过引用立即获取它，而不是在O(h)中计算每个给定节点的parent()。此外，每个节点的父节点只是对内存中另一个现有对象的引用。因此，空间复杂度也是O(1)。
当我们经常需要检索节点的父节点时，该版本的 BST 非常有用，因为Parent()操作经过了很好的优化。