- 此时这个最大值一定是在左树的最右边，意味着它肯定没有右子树
所以找到最小值的特征是：
- 此节点左子树为空，且一定在
cur右树的最左边 - 此节点右子树为空，且一定在
cur左树的最右边
寻找右子树的最小值
代码语言：java复制// 3.1 右数的最小值
TreeNode t = cur.right;
TreeNode tp = cur;
while (t.left != null) {
tp = t;
t = tp.left;
}
cur.val = t.val;
if(t == tp.right) {
//t 和 tp 在起始步就找到了最小值
tp.right = t.right;
}else{
//t 和 tp 在继续移动的过程中找到最小值
tp.left = t.right;
}t是用来定位最小值的，当t.left == null的时候，t就是最小值tp是用来定位t的父节点的，方便后续对节点进行删除（因为节点的删除都要依靠删除节点的父节点进行“改变连接对象”）- 在没找到最小节点之前，
tp和t一起进行移动 1. 最开始tp在要删除的节点cur的位置，t在cur的右节点（起始步） 2.tp走到t的位置 3.t再走向tp的左节点（一轮移动结束） 4.t.left != null，tp走到t的位置 5.t再走向tp的左节点（一轮移动结束） 6. ...... - 如果在起始步就满足
t.left == null了，则直接进行
完整代码
代码语言：java复制public void remove(int key) {
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
if (cur.val < key) {
parent = cur;
cur = cur.right;
} else if (cur.val > key) {
parent = cur;
cur = cur.left;
} else {
//此时就是找到了要删除的节点
removeNode(parent, cur);
return;
}
}
}
private void removeNode(TreeNode parent, TreeNode cur) {
// 1.当要删除的节点 cur 的左孩子为空
if (cur.left == null) {
if (cur == root) {
// 1.1 要删除的 cur 为根节点
root = cur.right;
} else if (cur == parent.left) {
// 1.2 要删除的 cur 是 parent 的左节点
parent.left = cur.right;
} else {
// 1.3 要删除的 cur 是 parent 的右节点
parent.right = cur.right;
}
// 2. 要删除的节点 cur 的右孩子为空
} else if (cur.right == null) {
if (cur == root) {
// 2.1 要删除的 cur 是根节点
root = cur.left;
} else if (cur == parent.left) {
// 2.2 要删除的 cur 是 parent 的左节点
parent.left = cur.left;
} else {
// 2.3 要删除的 cur 是 parent 的右节点
parent.right = cur.left;
}
// 3. 要删除的节点的左右孩子都不为空
} else {
// 3.1 右数的最小值
TreeNode t = cur.right;
TreeNode tp = cur;
while (t.left != null) {
tp = t;
t = tp.left;
}
cur.val = t.val;
if(t == tp.right) {
//t 和 tp 在起始步就找到了最小值
tp.right = t.right;
}else{
//t 和 tp 在继续移动的过程中找到最小值
tp.left = t.right;
}
}
}
