Insert a key in a binary search tree if the binary search tree does not already contain the key. Return the root of the binary search tree.

Assumptions

• There are no duplicate keys in the binary search tree

• If the key is already existed in the binary search tree, you do not need to do anything

Examples

    5

  /    \

3        8

/ \

1 4

insert 11, the tree becomes

    5

  /    \

3        8

/ \ \

1 4 11

insert 6, the tree becomes

    5

  /    \

3        8

/ \ / \

1 4 6 11

Solution: 不断与cur.key比较，找到null时新建node

  public TreeNode insert(TreeNode root, int key) {
    if (root == null) {
      return new TreeNode(key);
    }
    TreeNode cur = root;
    while (cur != null) {
      if (cur.key == key) {
        return root;
      }
      if (cur.key < key) {
        if (cur.right == null) {
          cur.right = new TreeNode(key);
          return root;
        } else {
          cur = cur.right;
        }
      } else {
        if (cur.left == null) {
          cur.left = new TreeNode(key);
          return root;
        } else {
          cur = cur.left;
        }
      }
    }
    return root;
  }