public TreeNode deleteNode(TreeNode root, int key) {
TreeNode preNode = null, curNode = root;
while (curNode != null && curNode.val != key) {
return getSuccessor(curNode);
else if (preNode.left == curNode) {
preNode.left = getSuccessor(curNode);
else if (preNode.right == curNode) {
preNode.right = getSuccessor(curNode);
public TreeNode getSuccessor(TreeNode node) {
if (node.right == null) {
TreeNode preNode = null, successor = node.right;
while (successor.left != null) {
successor = successor.left;
successor.left = node.left;
if (node.right != successor) {
preNode.left = successor.right;
successor.right = node.right;