递归删除二叉搜索树

思路：

• 要删除的节点为叶子节点，可以直接删除。

  

• 要删除的几点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。

  

• 要删除的节点不是叶子节点，且没有右节点但是有左节点。这意味着它的后继节点在它的上面，但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。

  

算法：

• 如果key > root.val，则说明要删除的节点在右子树，root.right = deleteNode(root.right,key);
• 如果key < root.val, 则说明要删除的节点在左子树，root.left = deleteNode(root.left,key);
• 如果key == root.val, 则说明当前节点就是要删除的节点,则：
  • 如果该节点是叶子节点，则直接删除它。root = null.
  • 如果该节点不是叶子节点且有右节点，则用他后继节点的值代替，root.val = successor.val.然后删除后继节点。
  • 如果该节点不是叶子节点且只有左节点，则用他的前驱节点的值代替，root.val = predecessor.val,然后删除前驱节点。
• 返回 root.

代码实现：

class Solution {
  /* One step right and then always left */
  public int successor(TreeNode root) {
    root = root.right;
    while (root.left != null) root = root.left;
    return root.val;
  }

  /* One step left and then always right */
  public int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null) root = root.right;
    return root.val;
  }

  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;

    // delete from the right subtree
    if (key > root.val) root.right = deleteNode(root.right, key);
    // delete from the left subtree
    else if (key < root.val) root.left = deleteNode(root.left, key);
    // delete the current node
    else {
      // the node is a leaf
      if (root.left == null && root.right == null) root = null;
      // the node is not a leaf and has a right child
      else if (root.right != null) {
        root.val = successor(root);
        root.right = deleteNode(root.right, root.val);
      }
      // the node is not a leaf, has no right child, and has a left child 
      else {
        root.val = predecessor(root);
        root.left = deleteNode(root.left, root.val);
      }
    }
    return root;
  }
}