[LintCode]Insert Node in Binary Search Tree

很简单题，每个node决定是往左还是往右还是就是这个节点。类似二分的做法。




代码如下：

recursive版本：

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param root: The root of the binary search tree.
	* @param node: insert this node into the binary search tree
	* @return: The root of the new binary search tree.
	*/
	public TreeNode insertNode(TreeNode root, TreeNode node) {
	// write your code here
	if (root == null)
	return node;
	if (node.val < root.val)
	root.left = insertNode(root.left, node);
	else if (node.val > root.val)
	root.right = insertNode(root.right, node);
	else
	root.val = node.val;
	return root;
	}
	}

view raw BST insertion recursion.java hosted with ❤ by GitHub

iterative版本：

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param root: The root of the binary search tree.
	* @param node: insert this node into the binary search tree
	* @return: The root of the new binary search tree.
	*/
	public TreeNode insertNode(TreeNode root, TreeNode node) {
	if (root == null)
	return node;
	TreeNode curr = root;
	while (true) {
	if (node.val < curr.val) {
	if (curr.left != null)
	curr = curr.left;
	else {
	curr.left = node;
	break;
	}
	} else if (node.val > curr.val) {
	if (curr.right != null)
	curr = curr.right;
	else {
	curr.right = node;
	break;
	}
	} else {
	curr.val = node.val;
	break;
	}
	}
	return root;
	}
	}

view raw BST insertion iterative.java hosted with ❤ by GitHub