/**
* 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) {
return delete(root, key);
}
private TreeNode delete(TreeNode node, int key) {
if (node == null) {
return null;
}
// 向右
if (key > node.val) {
node.right = delete(node.right, key);
return node;
}
// 向左
if (key < node.val) {
node.left = delete(node.left, key);
return node;
}
if (key == node.val) {
// 当前节点是叶子节点
if (node.left == null && node.right == null) {
return null;
}
// 当前节点没有左子树 返回右子树
if (node.left == null) {
return node.right;
}
// 当前节点没有右子树 返回左子树
if (node.right == null) {
return node.left;
}
// 当前节点左右子树都存在
// 找到右子树的最小值节点作为新节点
TreeNode newRoot = node.right;
while (newRoot.left != null) {
newRoot = newRoot.left;
}
// 将该节点从右子树中删除 同时 将左右子树赋值给新节点
newRoot.right = delete(node.right, newRoot.val);
newRoot.left = node.left;
// 或者，我们也可以将当前要删除的节点的左子树中最大值节点作为新节点
// TreeNode newRoot = node.left;
// while (newRoot.right != null) {
// newRoot = newRoot.right;
// }
// newRoot.left = delete(node.left, newRoot.val);
// newRoot.right = node.right;
return newRoot;
}
return node;
}
}