87.Remove Node in Binary Search Tree

1.Description(Hard)

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

    5
   / \
  3   6
 / \
2   4

Remove 3, you can either return:

    5
   / \
  2   6
   \
    4

or

    5
   / \
  4   6
 /
2

2.Code

https://lefttree.gitbooks.io/leetcode/binaryTree/removeNodeInBST.html

Delete node 有三种情况

因为要delete,在find这个node的过程中要保留一个parent的变量

1. leaf node

删掉这个node，把parent对这个node的reference设为null

1. Node with only one child

delete the node,把parent对node的reference link到node的child

1. Node with 2 children

   • find the minimum node of right subtree

   • replace the value of found node

   • delete the old duplicate node(case 1/2, cause minimum node should not have left child)

http://www.cnblogs.com/grandyang/p/6228252.html