LeetCode第450题：删除二叉搜索树中的节点的Java实现
摘要
LeetCode第450题要求从二叉搜索树（BST）中删除一个节点。本文将介绍两种Java实现方法：迭代法和递归法。
1. 问题描述
给定一个二叉搜索树（BST）的根节点和要删除的值。在删除节点后，返回 BST 的新根节点（可能与旧根节点相同）。题目保证要删除的节点一定存在于BST中。
2. 示例分析
输入：root = [5,3,6,2,4,null,null,1], val = 3
输出：[5,4,6,2,null,null,1]
3. 算法设计
3.1 递归法
递归法利用BST的性质，从根节点开始，找到要删除的节点，然后根据节点的子节点数量决定删除策略：
- 无子节点（叶子节点）：直接删除。
- 有一个子节点：用其子节点替换它。
- 有两个子节点：用其右子树的最小节点（或左子树的最大节点）替换它。
3.2 迭代法
迭代法使用一个栈来模拟递归过程，从根节点开始，逐层向下遍历，直到找到要删除的节点。
4. Java代码实现
4.1 递归法
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode temp = root.right;
while (temp.left != null) temp = temp.left;
root.val = temp.val;
root.right = deleteNode(root.right, temp.val);
}
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
4.2 迭代法
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root, parent = null;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
current = stack.pop();
if (current.val == key) {
if (parent.left == current) parent.left = current.right;
else if (parent.right == current) parent.right = current.right;
return root;
}
if (current.right != null) {
while (current.right != null) {
stack.push(current);
current = current.right;
}
}
parent = current;
current = current.right;
}
}
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
5. 代码解析
- 递归法：通过递归找到要删除的节点，然后根据其子节点的数量决定删除策略。
- 迭代法：使用栈模拟递归过程，逐层向下遍历，直到找到要删除的节点。
6. 测试验证
使用LeetCode平台或其他测试工具对提供的代码进行测试，确保算法的正确性。
7. 总结
LeetCode第450题是一个典型的二叉搜索树问题，通过理解BST的性质，可以有效地删除指定的节点。递归法和迭代法都是有效的解决方案。
8. 参考文献
原文地址：https://blog.csdn.net/2301_77695569/article/details/140577565
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！