701. Insert into a Binary Search Tree

基础递归，root左边右边要接住递归的返回值。

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    }
    else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

等价的写法：把if (root == null) return new TreeNode(val);替换成两句判断(其实是没有主意null时候代码的复用..)。

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root.val > val) {
        if (root.left == null) {
            root.left = new TreeNode(val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }
    } else {
        if (root.right == null) {
            root.right = new TreeNode(val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
    }
    return root;
}

iteration，相当于插入链表，快但代码多且乱。

public TreeNode insertIntoBST(TreeNode root, int val) {
    TreeNode node = new TreeNode(val),
                cur = root;
    while (cur != null) {
        if (cur.val > val) {
            if (cur.left != null) {
                cur = cur.left;
            } else {
                cur.left = node;
                break;
            }
        } else {
            if (cur.right != null) {
                cur = cur.right;
            } else {
                cur.right = node;
                break;
            }
        }
    }
    return root;
}