二叉搜索树操作：查找最近公共祖先、节点插入与删除
寻找二叉搜索树的最近公共祖先
问题描述：
以下代码实现包含了第二种情况（节点自身作为公共祖先）的解决方案。
递归解法：
class BSTAncestorFinder {
public TreeNode findCommonAncestor(TreeNode treeRoot, TreeNode node1, TreeNode node2) {
if (treeRoot == null) {
return null;
}
if (treeRoot.value > node1.value && treeRoot.value > node2.value) {
return findCommonAncestor(treeRoot.leftChild, node1, node2);
}
if (treeRoot.value < node1.value && treeRoot.value < node2.value) {
return findCommonAncestor(treeRoot.rightChild, node1, node2);
}
return treeRoot;
}
}
迭代解法：
class BSTAncestorFinder {
public TreeNode findCommonAncestor(TreeNode treeRoot, TreeNode node1, TreeNode node2) {
while (treeRoot != null) {
if (treeRoot.value > node1.value && treeRoot.value > node2.value) {
treeRoot = treeRoot.leftChild;
} else if (treeRoot.value < node1.value && treeRoot.value < node2.value) {
treeRoot = treeRoot.rightChild;
} else {
return treeRoot;
}
}
return treeRoot;
}
}
在二叉搜索树中插入新节点
问题描述：
关键点： 存在多种可能的插入位置，我们只需实现一种即可。最简单的方式是将新节点插入为叶子节点。这意味着插入操作总是发生在树的底部。
class BSTInserter {
public TreeNode insertNode(TreeNode treeRoot, int newValue) {
if (treeRoot == null) {
return new TreeNode(newValue);
}
if (treeRoot.value > newValue) {
treeRoot.leftChild = insertNode(treeRoot.leftChild, newValue);
} else if (treeRoot.value < newValue) {
treeRoot.rightChild = insertNode(treeRoot.rightChild, newValue);
}
return treeRoot;
}
}
从二叉搜索树中删除节点
问题描述：
此问题有一定难度，需要考虑多种情况
五种情况分析：
- 未找到要删除的节点
- 要删除的节点是叶子节点（左右子节点都为空）
- 左子节点非空，右子节点为空
- 左子节点为空，右子节点非空
- 左右子节点都不为空。采用右子树继承策略，需要将左子树移至右子树的最左节点（即比被删除节点值稍大的节点）
class BSTNodeRemover {
public TreeNode removeNode(TreeNode treeRoot, int keyValue) {
if (treeRoot == null) {
return null;
}
// 终止条件
if (treeRoot.value == keyValue) {
if (treeRoot.leftChild == null && treeRoot.rightChild == null) {
return null;
} else if (treeRoot.leftChild != null && treeRoot.rightChild == null) {
return treeRoot.leftChild;
} else if (treeRoot.leftChild == null && treeRoot.rightChild != null) {
return treeRoot.rightChild;
} else {
// 选择右子树继承
TreeNode current = treeRoot.rightChild;
while (current.leftChild != null) {
current = current.leftChild;
}
current.leftChild = treeRoot.leftChild; // 将左子树移至右子树最左节点的左侧
return treeRoot.rightChild;
}
}
// 递归逻辑。到这里说明 treeRoot.value != keyValue
if (treeRoot.value > keyValue) {
treeRoot.leftChild = removeNode(treeRoot.leftChild, keyValue);
} else {
treeRoot.rightChild = removeNode(treeRoot.rightChild, keyValue);
}
return treeRoot;
}
}
总结
二叉搜索树的相关问题，通常使用迭代方法更为简便。（由于 BST 的有序特性，迭代解法不需要使用栈结构）
