LeetCode75-450-Delete-Node-in-BST

🧠 Summary of Thoughts

1. Locate key in BST, use the property of BST below:

   BST property: leftNode < root < rightNode

   • if key < root.val, then call left tree recursively
   • if key > root.val, then call right tree recursively
2. If the key node is found, then delete:
   • if there is NO left tree, then return the right tree
   • if there is NO right tree, then return the left tree
   • if left and right tree are exist:
     • find the leftmost of the right tree, and use this value to replace the previous node key

✅ Code（Java）

class Solution {
    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) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = minNode(root.right);
                root.val = min.val;
                root.right = deleteNode(root.right, min.val);
            }
        }
        return root;
    }
    private TreeNode minNode(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}