LeetCode 450. Delete Node in a BST

问题描述

• Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
• Basically, the deletion can be divided into two stages:
  Search for a node to remove.
  If the node is found, delete the node.
• Note: Time complexity should be O(height of tree).

• Example :
  

• 地址

问题分析

• 如何在一棵二叉搜索树中删除给定值的相应节点?（默认该BST中一定存在该节点）
• 先明确函数的意义：在一棵BST中删除给定值的相应节点，然后返回删除后的根节点
• 首先，若想删除该节点，必须找到该节点，所以首先应递归删除该节点。
• 然后，若找到该节点之后（递归的base case），分情况讨论 ：
  
  • 如果该节点是叶子节点，那么直接返回null
  • 如果该节点只有一个孩子，那么“子承父业”，返回该孩子
  • 如果该节点有两个孩子，为了保证删除后依旧是BST,那么必须找待删除节点的中序遍历的前驱节点或者后继节点来取代该孩子。在BST中，一个节点的前驱节点是它的左子树的最右节点，一个节点的后继节点是它的右子树的最左节点。假设找到后继节点，用后继节点的值取代待删除节点，然后在右子树中递归删除该后继节点即可。通过值的取代，实现了另类的删除

经验教训

• 在BST中查找，插入，删除，找最大值，找最小值，floor，ceil 都是 O(logN)的时间复杂度
• 对于二叉搜索树中的插入操作
  
  • 可以递归插入，base case 便是当root == null时，直接创建节点，并返回，否则，若key < root.val,就需要 root.left = insert(root.left, key),相应的，若key > root.val,就需要 root.right = insert(root.right, key),注意inset 操作的返回值是插入后的BST的根节点
  • 同样也可以先用类似于 find 操作，找到待插入节点的父节点，然后根据大小，连在其后即可。
• 二叉搜索树的删除操作，此文已经介绍

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //在以root为根的二叉树中删除值为key的节点，并返回删除后的头结点
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) { //继续在左子树递归删除
            root.left = deleteNode(root.left, key);
        }else if (key > root.val) { //继续在右子树递归删除
            root.right = deleteNode(root.right, key);
        }else {
            //找到了该节点
            if (root.left != null && root.right != null) {
                //若该节点存在左右子树，那么用右子树中最小的那个节点(后继)取代他，然后在右子树中删除最小的那个节点
                TreeNode minOfRight = findMin(root.right);
                root.val = minOfRight.val;
                root.right = deleteNode(root.right, minOfRight.val);
            }else {
                //若该节点为叶子结点，或者只有一个孩子，可直接返回那个孩子（叶子节点时为null）。
                if (root.left == null) {
                    return root.right;
                }
                if (root.right == null) {
                    return root.left;
                }
            }
        }
        return root;
    }

    //找root为根的BST的最小节点
    public TreeNode findMin(TreeNode root) {
        if(root == null) {
            return null;
        }
        while(root.left != null) {
            root = root.left;
        }
        return root;
    }
}