深度优先遍历 DFS
解题思路
二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整，索引删除节点比增加节点复杂的多；
删除节点一共有五种情况：
- 第一种：没找到要删除的节点
- 第二种：需要删除的目标节点 target 的左右节点都为空，即叶子节点，无需处理；
- 第三种：需要删除的目标节点 target 的左节点为空，右节点不为空，则直接让 父结点指向 target.right 结点 即可；
- 第四种：需要删除的目标节点 target 的右节点为空，左节点不为空，则直接让 父结点指向 targte.left 结点 即可；
- 第五种：需要删除的目标节点 target 的左右节点都不为空，将 target.left 的树枝放到 target.right 的左子树最后一个左节点之后；
复杂度
-
时间复杂度：
O(n)，其中 n 为 root 的节点个数；最差情况下，寻找和删除 successor 各需要遍历一次树； -
空间复杂度：
O(n)，其中 n 为 root 的节点个数，递归的深度最深为O(n)；
实现代码
var deleteNode = function (root, key) {
// 第一种：没找到要删除的节点
if (root === null) return root;
// key 小于当前节点的值，要继续向左子树寻找
if (root.val > key) root.left = deleteNode(root.left, key);
// key 大于当前节点的值，要继续向右子树寻找
if (root.val < key) root.right = deleteNode(root.right, key);
if (root.val === key) {
// 第二种：需要删除的目标节点 target 的左右节点都为空，即叶子节点，无需处理；
if (root.left === null && root.right === null) return null;
// 第三种：需要删除的目标节点 target 的左节点为空，右节点不为空，则直接让 父结点指向 targte.right 结点 即可；
if (root.left === null) return root.right;
// 第四种：需要删除的目标节点 target 的右节点为空，左节点不为空，则直接让 父结点指向 targte.left 结点 即可；
if (root.right === null) return root.left;
// 第五种：需要删除的目标节点 target 的左右节点都不为空，将 target.left 的树枝放到 target.right 的左子树最后一个左节点之后；
let curr = root.right;
while (curr.left) curr = curr.left;
curr.left = root.left;
return root.right;
}
return root;
};
广度优先遍历 BFS
复杂度
-
时间复杂度：
O(n)，其中 n 为 root 的节点个数，最差情况下，需要遍历一次树； -
空间复杂度：
O(1)；
实现代码
var deleteNode = function (root, key) {
// 第一种：没找到要删除的节点
if (root === null) return root;
let cur = root;
let pre = null; // 记录 cur 的父节点，用来删除 cur
while (cur) {
if (cur.val === key) break;
pre = cur;
cur.val > key ? cur = cur.left : cur = cur.right;
}
// 只有一个节点的情况，pre 就是 null
if (pre === null) return deleteOneNode(cur);
// 删除左孩子
if (pre.left && pre.left.val === key) pre.left = deleteOneNode(cur);
// 删除右孩子
if (pre.right && pre.right.val === key) pre.right = deleteOneNode(cur);
return root;
}
const deleteOneNode = target => {
// 第二种：需要删除的目标节点 target 的左右节点都为空，即叶子节点，无需处理；
if (target === null) return null;
// 第三种：需要删除的目标节点 target 的左节点为空，右节点不为空，则直接让 父结点指向 targte.right 结点 即可；
if (target.left === null) return target.right;
// 第四种：需要删除的目标节点 target 的右节点为空，左节点不为空，则直接让 父结点指向 targte.left 结点 即可；
if (target.right === null) return target.left;
// 第五种：需要删除的目标节点 target 的左右节点都不为空，将 target.left 的树枝放到 target.right 的左子树最后一个左节点之后；
let cur = target.right;
while (cur.left) cur = cur.left;
cur.left = target.left;
return target.right;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 230. 二叉搜索树中第 k 小的元素
上一篇
评论
