450. Delete Node in a BST - Medium

前往題目

想法

• 找到目標後直接刪除，把parent直接接到他的子樹

思路

但這樣的想法有點問題，因為沒有考慮到樹的右子樹必須要大於父節點

Recursion

1. 遇到null直接回傳root，回傳null也行，反正都是同樣的值
2. 接著就看當前節點是否是Key，大於的話就往左邊繼續搜尋，反之往右邊
3. 如果找到同樣的值，只有左或者右一個子樹的時候直接捨棄當前節點，接上子樹就好
4. 如果他同時有右子樹和左子樹，那就往右子樹搜尋最小值，並把那個值放到當前節點，並且把右子樹那個最小值刪除，並同時保證是BST

Code

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

        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else { // Found the value
            // When only 1 child, just delete the current node
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Find the min value of the right subtree(since the parent is smaller than its right children) and put it in the parent
            TreeNode cur = root.right;
            
            // Keep going to the left child of the right subtree(smallest number)
            while (cur.left != null) {
                cur = cur.left;
            }
            
            // Change the current value to the smallest of the right subtree
            root.val = cur.val;
            // Delete the current(original) value 
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
}