@@ -0,0 +1,1230 @@
+// Solution runs in O(h) time and O(h) space, where h is the height of the binary search tree.%0A/**%0A * Definition for a binary tree node.%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Aclass Solution %7B%0A  public TreeNode deleteNode(TreeNode root, int key) %7B%0A    if (root == null) return root;%0A    if (root.val %3E key) %7B%0A      root.left = deleteNode(root.left, key);%0A      return root;%0A    %7D else if (root.val %3C key) %7B%0A      root.right = deleteNode(root.right, key);%0A      return root;%0A    %7D else %7B%0A      TreeNode right = root.right;%0A      // 1. root is the largest node, return left subtree%0A      if (right == null) return root.left;%0A      // 2. root.right is the smallest node in the right subtree, use it as new root%0A      if (right.left == null) %7B%0A        right.left = root.left;%0A        return right;%0A      %7D%0A      // find the smallest node in the right subtree to use as new root%0A      // and relink it%0A      while (right.left.left != null) %7B%0A        right = right.left;%0A      %7D%0A      TreeNode L = right;%0A      TreeNode T = right.left;%0A      L.left = T.right;%0A      T.right = root.right;%0A      T.left = root.left;%0A      return T;%0A    %7D%0A  %7D%0A%7D%0A

add solution