leetcode450.删除二叉搜索树中的节点：迭代法巧用中间节点应对多场景删除

一、题目深度解析与BST特性剖析

在二叉搜索树（BST）中删除节点，需确保删除操作后树依然保持BST特性。题目要求我们根据给定的节点值key，在BST中删除对应节点。BST的核心特性是左子树所有节点值小于根节点值，右子树所有节点值大于根节点值，这一特性为我们提供了高效定位和处理待删除节点的思路。删除节点时，由于节点在树中的位置不同，可能存在多种情况，合理利用BST特性判断场景，并通过中间节点辅助处理，是解决问题的关键。

二、迭代解法的完整代码与逻辑框架

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root == null){return null;}TreeNode pre = root;TreeNode cur = root;while(cur != null){if(cur.val > key){pre = cur;cur = cur.left;}else if(cur.val < key){pre = cur;cur = cur.right;}else{if(cur == pre.left){pre.left = deleteOneNode(cur);break;}else if(cur == pre.right){pre.right = deleteOneNode(cur);break;}else{return deleteOneNode(cur);}}}return root;}public TreeNode deleteOneNode(TreeNode root){if(root == null){return root;}if(root.left == null){return root.right;}else if(root.right == null){return root.left;}else{TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;root = root.right;return root;}}
}

核心变量与逻辑设计

1. pre与cur节点：
   • pre节点用于记录cur节点的父节点，在找到待删除节点后，pre可辅助将删除节点后的子树重新连接到原树中。
   • cur节点用于遍历树，通过比较cur.val与key，在BST中定位待删除节点。
2. deleteOneNode方法：专门处理删除节点的具体逻辑，针对待删除节点的不同子树情况进行处理，确保删除后树的BST特性不变。

三、核心问题解析：场景判断与中间节点的作用

1. 利用BST特性定位待删除节点

在BST中，我们可以通过比较节点值与key的大小关系，高效定位待删除节点。代码中通过while循环实现：

while(cur != null){if(cur.val > key){pre = cur;cur = cur.left;}else if(cur.val < key){pre = cur;cur = cur.right;}else{// 找到待删除节点，进入处理逻辑}
}

当cur.val > key时，根据BST特性，待删除节点必然在cur的左子树中，因此将pre更新为cur，cur移动到其左子树继续查找；当cur.val < key时，待删除节点在cur的右子树中，同样更新pre和cur继续查找；若cur.val == key，则找到了待删除节点，进入后续处理逻辑。

2. 多场景判断与中间节点辅助处理

找到待删除节点后，根据其在树中的位置以及子树情况，存在多种处理场景：

• 待删除节点是父节点的左子节点：

if(cur == pre.left){pre.left = deleteOneNode(cur);break;
}

此时，通过pre节点找到待删除节点的父节点，将父节点的左子树更新为删除cur节点后的子树，即调用deleteOneNode(cur)的返回结果。

• 待删除节点是父节点的右子节点：

else if(cur == pre.right){pre.right = deleteOneNode(cur);break;
}

与左子节点情况类似，将父节点的右子树更新为删除cur节点后的子树。

• 待删除节点是根节点：

else{return deleteOneNode(cur);
}

直接调用deleteOneNode(cur)处理根节点的删除，并返回处理后的新根节点。

3. deleteOneNode方法的场景处理

deleteOneNode方法进一步针对待删除节点的子树情况进行处理：

• 待删除节点无左子树：

if(root.left == null){return root.right;
}

此时，直接返回其右子树，将右子树连接到原父节点对应位置，这样既保证了删除节点，又维持了BST特性。

• 待删除节点无右子树：

else if(root.right == null){return root.left;
}

与无左子树情况类似，返回其左子树连接到原父节点对应位置。

• 待删除节点左右子树均存在：

else{TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;root = root.right;return root;
}

此时，需要找到待删除节点右子树中的最小节点（最左节点），将原左子树连接到该最小节点的左子树位置，然后将待删除节点的右子树作为新的子树返回。这样操作后，树依然保持BST特性，因为右子树最小节点大于原左子树所有节点，小于原右子树其他节点。

四、迭代流程深度模拟：以具体示例BST展示操作过程

假设我们有如下BST：

        5/ \3   6/ \   \2   4   7

我们要删除节点值为3的节点。

1. 定位待删除节点：
   • 初始时，pre = root = 5，cur = root = 5。
   • 因为3 < 5，所以pre = 5，cur = cur.right = 3。此时找到了待删除节点，且cur是pre的左子节点。
2. 处理删除节点：
   • 由于cur是pre的左子节点，执行pre.left = deleteOneNode(cur)。
   • 进入deleteOneNode方法，cur节点左右子树均存在，找到cur右子树的最小节点4，将cur的左子树2连接到4的左子树，即4.left = 2，然后返回cur的右子树，也就是4。
   • 此时pre.left（即5.left）更新为4，完成节点删除操作。
3. 删除后的BST：

        5/ \4   6/     \2       7

五、算法复杂度分析

1. 时间复杂度

在定位待删除节点过程中，每次比较都能排除一半的子树，时间复杂度为O(h)，其中h为树的高度。在平衡BST中，h = logn（n为节点数），时间复杂度为O(logn)；在最坏情况下，树退化为链表，h = n，时间复杂度为O(n)。处理删除节点的操作，无论是哪种场景，都只涉及常数次指针操作，时间复杂度也为O(h)。因此，整体时间复杂度为O(h)。

2. 空间复杂度

算法使用了常数个额外的指针变量（pre和cur等），空间复杂度为O(1)，不随树的规模变化而增加。

六、核心技术点总结：迭代删除的关键要素

1. BST特性的深度运用：通过节点值大小比较，高效定位待删除节点，减少不必要的遍历。
2. 多场景判断策略：根据待删除节点在树中的位置以及子树情况，细致区分不同场景，分别进行处理，确保删除操作的正确性。
3. 中间节点的巧妙辅助：pre和cur节点的设置，在定位和处理删除节点过程中发挥了重要作用，使子树的重新连接更加清晰和高效。

七、常见误区与优化建议

1. 错误的指针操作

在处理子树连接时，容易出现指针指向错误，例如在将右子树最小节点与原左子树连接时，误将右子树最小节点的右子树连接原左子树。应仔细确认指针操作，确保连接关系正确。

2. 忽略边界情况

在代码中，虽然对空树情况进行了处理，但在实际应用中，还需注意其他边界情况，如树中只有一个节点时的删除操作，确保代码的健壮性。

3. 优化建议

可以考虑使用更简洁的代码结构，减少重复逻辑，例如将deleteOneNode方法中的部分逻辑提取为公共方法，提高代码的复用性和可读性。同时，在性能要求较高的场景下，可结合更复杂的数据结构或算法进一步优化删除操作的效率。

通过以上对迭代法删除二叉搜索树节点的详细分析，我们深入理解了如何利用BST特性和中间节点，高效、准确地处理删除操作。这种方法在实际应用中具有重要的参考价值，能够帮助我们更好地解决类似的树结构处理问题。