每日一题~删除二叉搜索树中的节点

原题链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

题目描述：

思路分析：

由题可知，这是一个二叉搜索树，我们删除掉一个节点之后，需要重新调整树，使其仍然是二叉搜索树，那么我们接下来分析一下有多少中删除的情况。

1、删除节点的左子树为空，此时我们只需要让它的父节点指向它的右子树就可以了；

2、删除节点的右子树为空，当右子树为空的时候，情况和左子树相似，我们直接让它的父节点指向它的左子树就可以了；

3、删除节点的左子树和右子树都不为空，和题目中所给的例子相同，题目中给了两种结果，我们都分析一下

①

我们可以看到删除掉目标节点之后,父节点指向了右子树，右子树的节点指向了左子树，看似简单的调整。其实不完全是这样，只是因为这里左右两边都只有一个节点，完整的步骤是，先找到右子树的最小节点，也就是右子树最左边的节点，然后让这个节点指向左子树，最后让父节点指向右子树。代码如下：

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

② 

第二种结果是父节点指向左子树，左子树指向右子树。这个步骤与第一种情况的步骤相似，只是将左右颠倒了，完整的步骤是，先找到左子树的最大节点，也就是左子树最右边的节点，然后让这个节点指向右子树，最后让父节点指向左子树。代码如下：

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

4、删除节点的左右子树都为空时，这种情况在左右子树都存在的情况下已经得到了解决，

root = root.left 或者 root = root.right 都成功删掉了目标节点，所以我们不需要再单独为这一情况做处理。

代码示例：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
      if(root == null) return null;
      if(root.val == key) {
        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;
        }
      }
      if(root.val > key) root.left = deleteNode(root.left,key);
      else if(root.val < key) root.right = deleteNode(root.right,key);
      return root;
    }
}