Home Computer Science Java Algorithm

[[Lintcode problems]]
Level: #medium
Time Complexity: O(h)
Space Complexity: O(1)
URL: 1234 · Delete Node in a BST - LintCode

# Description

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:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Example 1:

Input:
{5,3,6,2,4,#,7}
3
Output:
{5,4,6,2,#,#,7} or {5,2,6,#,4,#,7} or another vaild answer

Explanation:
The tree is 
    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,#,#,7}, shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is {5,2,6,#,4,#,7}.

    5
   / \
  2   6
   \   \
    4   7

Example 2:

Input:
{1}
1
Output:
{}

# Solution

這題考的是二叉搜索樹的刪除操作，考點在刪除節點後，仍然要保持二叉搜索樹的結構。

分了以下幾種情況

  1. 要刪的節點是葉子節點，沒有兒子，只有它一個，可以直接設為空。

  2. 要刪除的節點 target 有左子節點

    1. 找到 target 的左邊節點的最大值替換當前節點 target ，也就是第一個小於它的數。
    2. 換完要移除左子節點的最大值，那麼就等於現在要刪的是 左子節點的最大值 ，可以往下递歸刪除。（記得 BST 最左下角的值，對整顆樹來說是最小）

  3. 要刪除的節點 target 有左子節點

    1. 找到 target 的右邊節點的最小值替換當前節點 target ，也就是第一個大於它的數。
    2. 換完要移除右子節點的最大值，那麼就等於現在要刪的是 右子節點的最小值 ，可以往下递歸刪除。 （記得 BST 最右下角的值，對整顆樹來說是最大）

  4. target 有左兒子和右兒子

    1. 可以二選一：
      1. 找它左兒子最大值
      2. 或 找它右兒子最小值

# Code

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the BST
     * @param key: The number needed to be deleted
     * @return: The root of the BST
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        // 樹裡沒有東西時，返回 null
        if(root == null){
            return null;
        }
        //key 是小於根節點時，往左邊找
        if(key < root.val){ 
            root.left = deleteNode(root.left, key);
            return root;
        } else if (key > root.val) { //key > 根節點時往右找
            root.right = deleteNode(root.right, key);
            return root;
        } else { // 當前 root node 是等於 key 的時候
            if(root.right == null && root.left == null){
                root = null;
            } else if (root.right != null){
                root.val = findRightMin(root);
				// 把替換掉的節點递歸刪除
                root.right = deleteNode(root.right, root.val);
            } else { // 剩下的兩種情況：1）root.left!=null 
						//          2）root 有左右兒子時
                      // 當根左右都有時，找右邊最小 / 找左邊最大值的都行。
                root.val = findLeftMax(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }
    public int findRightMin(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
      public int findLeftMax(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
   
}