原题链接在这里：https://leetcode.com/problems/delete-node-in-a-bst/?tab=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:
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7]
key = 3
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,null,null,7], shown in the following BST.
5
/ 4 6
/ 2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/ 2 6
\ 4 7
题解：
根据BST的特性找key的TreeNode node. 然后delete掉. 有几种情况:
找不到, return null.
node.left == null, return node.right.
node.right == null, return node.left.
左右都不为空，找node的successor, swap value, 然后delete掉successor.
Time Complexity: O(h). Space: O(h), stack sapce.
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public TreeNode deleteNode(TreeNode root, int key) { 12 if(root == null){ 13 return root; 14 } 15 if(key < root.val){ 16 root.left = deleteNode(root.left, key); 17 }else if(key > root.val){ 18 root.right = deleteNode(root.right, key); 19 }else{ 20 if(root == null){ 21 return root; 22 }else if(root.left == null){ 23 return root.right; 24 }else if(root.right == null){ 25 return root.left; 26 }else{ 27 TreeNode suc = findSuc(root.right); 28 root.val = suc.val; 29 root.right = deleteNode(root.right, suc.val); 30 } 31 } 32 return root; 33 } 34 35 private TreeNode findSuc(TreeNode root){ 36 while(root.left != null){ 37 root = root.left; 38 } 39 return root; 40 } 41 }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/6484519.html