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 递归法

1. public class Solution {
2.     public TreeNode deleteNode(TreeNode root, int key) {
3.         if (root == null) return null;
4.         if (key < root.val) root.left = deleteNode(root.left, key);
5.         else if (key > root.val) root.right = deleteNode(root.right, key);
6.         else {
7.             if (root.left == null) return root.right;
8.             if (root.right == null) return root.left;
9.             
10.             TreeNode temp = root.right;
11.             while (temp.left != null) temp = temp.left;
12.             root.val = temp.val;
13.             root.right = deleteNode(root.right, temp.val);
14.         }
15.         return root;
16.     }
17. }
19. class TreeNode {
20.     int val;
21.     TreeNode left;
22.     TreeNode right;
23.     TreeNode(int x) { val = x; }
24. }

复制代码

4.2 迭代法

1. public class Solution {
2.     public TreeNode deleteNode(TreeNode root, int key) {
3.         if (root == null) return null;
4.         
5.         Stack<TreeNode> stack = new Stack<>();
6.         TreeNode current = root, parent = null;
7.         
8.         while (current != null || !stack.isEmpty()) {
9.             if (current != null) {
10.                 stack.push(current);
11.                 current = current.left;
12.             } else {
13.                 current = stack.pop();
14.                 if (current.val == key) {
15.                     if (parent.left == current) parent.left = current.right;
16.                     else if (parent.right == current) parent.right = current.right;
17.                     return root;
18.                 }
19.                 if (current.right != null) {
20.                     while (current.right != null) {
21.                         stack.push(current);
22.                         current = current.right;
23.                     }
24.                 }
25.                 parent = current;
26.                 current = current.right;
27.             }
28.         }
29.         return root;
30.     }
31. }
33. class TreeNode {
34.     int val;
35.     TreeNode left;
36.     TreeNode right;
37.     TreeNode(int x) { val = x; }
38. }

复制代码

5. 代码剖析

• 递归法：通过递归找到要删除的节点，然后根据其子节点的数目决定删除计谋。
  
• 迭代法：使用栈模拟递归过程，逐层向下遍历，直到找到要删除的节点。
  

6. 测试验证

使用LeetCode平台或其他测试工具对提供的代码举行测试，确保算法的准确性。
7. 总结

LeetCode第450题是一个典范的二叉搜索树标题，通过明白BST的性子，可以有用地删除指定的节点。递归法和迭代法都是有用的办理方案。
8. 参考文献

• LeetCode第450题官方题解
  
• 二叉搜索树的删除使用
  

---