前言
今天顺手复习了一下二叉搜索树的删除操作，发现没办法一边写出来buffree的代码了，有些生疏，顺手在记录一篇。
题目
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
题目拆解
这道题也是一道基本功题目，考验对二叉搜索树的性质以及基本操作的掌握程度，所以，没能五分钟写出bugfree的代码，就是基本功不扎实...要反省...
废话不多说 ，还是复习一下什么是二叉搜索树及其性质
- 二叉搜索树是一个自带了排序关系的一颗二叉树
- 每一个节点的左节点的值比当前节点值小，每一个节点的右节点的值比当前节点大
- 二叉搜索树的中序遍历结果是有序数组
这道题目就是删除一个指定的节点，考察的也就是在删除节点之后还要保证节点平衡。
所以，步骤分两步，
- 找到节点
- 删除节点
找到节点
- 如果目标值比当前节点值小，根据二叉搜索树性质，往左找。
- 如果目标值比当前节点值大，根据二叉搜索树性质，往右找。
- 如果当前节点值和目标值相等，要执行删除操作。
删除节点
这里也要考虑被目标节点的情况，分为这几种
- 要删除的节点是叶子节点，不用顾虑直接删除
- 要删除的节点左子树不为空，用前驱节点替换当前节点。
- 要删除的节点右子树不为空，用后继节点替换当前节点。
其实这里还有一种思路，
- 要删除的节点是叶子节点，不用顾虑直接删除
- 左右子树有一个为空，用不为空的子节点替换当前节点。
- 左右子树都不为空，前驱节点或者后续节点替换当前节点。
两种思路差不多，第二种写代码的时候需要在递归中带着父节点，不然没办法直接将子节点替换为当前节点，今天用第一种思路来做。
这里说到了两个概念，前驱节点和后续节点，其实也很好理解，上面说到了二叉搜索树的一个性质是中序遍历是有序的，所以一个节点的前驱节点就是中序遍历结果中，该节点前面的那个节点，同理，在中序遍历中紧挨着当前节点的下一个节点，就是后续节点。
再多说一句，二叉搜索树中，一个节点的前驱节点就是左子树的最右节点，也是左子树的最大节点，这就是中序遍历时，那个前驱节点的位置了。同理，后继也是一样。
接下来，直接看代码吧
代码
class Solution {
public TreeNode deleteNode(TreeNode root, int val) {
// 处理当前节点
if (root == null) {
return null;
}
if (root.val == val) {
// 如果两个子节点都是null,说明是叶子节点,直接删除即可
if (root.left == null && root.right == null) {
root = null;
} else if (root.right != null) {
// 如果右子树不为空,找到后继节点,替换
root.val = findMinNode(root).val;
root.right = deleteNode(root.right, root.val);
} else {
// 如果左子树不为空,找到前驱节点,替换
root.val = findMaxNode(root).val;
root.left = deleteNode(root.left, root.val);
}
} else if (val < root.val) {
// 处理左子树
root.left = deleteNode(root.left, val);
} else {
// 处理右子树
root.right = deleteNode(root.right, val);
}
return root;
}
TreeNode findMaxNode(TreeNode root) {
// 找最大值,往左走一步,然后一路往右走到头
TreeNode res = root.left;
while (res.right != null) {
res = res.right;
}
return res;
}
TreeNode findMinNode(TreeNode root) {
// 找最小值,往右走一步,然后一路往左走到头
TreeNode res = root.right;
while (res.left != null) {
res = res.left;
}
return res;
}
}
总结
基本功还是要掌握，二叉树基本的增删改查，二叉搜素树的增删改查，找前驱，找后继，基本功扎实了，才能更快速的解题。
网友评论