leetcode

LeetCode 450. Delete Node in a BST

Problem

LeetCode 450. Delete Node in a BST

1. 题目简述

给出一棵BST树，删除其中一个值为key的节点，返回新的树的根节点。例如：

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

2. 算法思路

中序遍历

对于一棵BST树，其最重要的性质就是其有序性。删除一个节点后，整棵树仍然保持有序。在这里我们需要明确一个节点的前驱结点（Predecessor）和后继节点（Successor）。某节点的前驱结点就是中序遍历的情况下在该节点之前的一个节点，后继节点就是该节点之后的一个节点。

删除一个节点时，需要将它的前驱结点或后继节点填补到它原本的位置上。那么逻辑就很清晰了，有几种不同的节点情况，我们分情况讨论。

  1. 删除的节点为叶子节点：直接删除，毫无压力。
  2. 删除的节点存在右子树：找到右子树的最小节点（后继节点），将该节点替换到删除节点的位置。
  3. 删除的节点为非叶子节点，且不存在右子树：找到左子树的最大节点（前驱节点），将该节点替换到删除节点的位置

或者我们可以遵循另一种思路：

  1. 删除的节点存在右子树：找到右子树的最小节点，替换为当前节点。
  2. 删除的节点不存在右子树，直接将左孩子替换为当前节点。

3. 解法

  1. 解法1：递归
/**
 * 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 {
  /*
  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;
  }
}
  1. 解法2：记录前驱结点
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 这里我分为两种情况讨论吧，看blog都是三种情况，不知道可行与否
        // 1. 存在右子树：将右子树中最小值替换掉当前值
        // 2. 不存在右子树：将左子树替换掉

        TreeNode pre = null, node = root;
        while (node != null && node.val != key) {
            if (node.val < key) {
                pre = node;
                node = node.right;
            } else if (node.val > key) {
                pre = node;
                node = node.left;
            }
        }
        if (node == null) {
            return root;
        }

        if (node.right == null) {
            // 如果是根节点
            if (pre == null) {
                return node.left;
            }
            // 右子树为空
            if (pre.val < node.val) {
                pre.right = node.left;
            } else {
                pre.left = node.left;
            }
        } else {
            // 右子树不为空
            TreeNode rightRoot = node.right, rightPre = null;
            while (rightRoot.left != null) {
                rightPre = rightRoot;
                rightRoot = rightRoot.left;
            }
            node.val = rightRoot.val;
            if (rightPre != null) {
                rightPre.left = rightRoot.right;
            } else {
                node.right = rightRoot.right;
            }
        }

        return root;
    }
}