/**
 * BST中删除一个节点，并返回新的BST
 * @author zhaizhg
 *
 */
public class DeleteNumInBST {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(5);
		root.left = new TreeNode(2);
		root.right = new TreeNode(6);
		root.left.left = new TreeNode(1);
		root.right.right = new TreeNode(7);
		root.left.right = new TreeNode(4);
		root.left.right.left = new TreeNode(3);
		TreeNode node = delete(root, 2);
		System.out.println(node.left.val);

	}
	
	static TreeNode delete(TreeNode node, int num) {
		if (node == null) return null;
		if (node.val == num) {
			// 如果没有左右子节点
			if (node.left == null && node.right == null) return null;
			// 如果没有左节点
			if (node.left == null) return node.right;
			// 如果没有右节点
			if (node.right == null) return node.left;
			// 如果左右节点都有,找到左或右子树的最小节点来替换他的位置
			// 再把这个最小节点给移除
			TreeNode minNode = getMin(node.right);
			node.val = minNode.val;
			node.right = delete(node.right, minNode.val);
		} else if (node.val > num) {
			node.left = delete(node.left, num);
		} else if (node.val < num) {
			node.right = delete(node.right, num);
		}
		return node;
			
	}
	
	static TreeNode getMin(TreeNode node) {
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

}