Insert Node in a Binary Search Tree

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

http://www.lintcode.com/en/problem/insert-node-in-a-binary-search-tree/

Discussion

这个题目比较简单，递归非递归的都要熟。构建一个BST也是用这个方法。对于递归来说，如果根为NULL，返回这个新的node，不然就令root的left或者right为递归调用返回的节点。
对于迭代，找到插入的位置，一定是一个空叶子节点，记住该叶子的父亲节点，链接node。

Solution

优雅的递归

class Solution {
public:
    /**
     * @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.
     */
    TreeNode* insertNode(TreeNode* root, TreeNode* node) {
        // write your code here
        if(root == NULL)
            return node;
        if(root->val > node->val) {
            root->left = insertNode(root->left, node);
        } 
        if(root->val < node->val) {
            root->right = insertNode(root->right, node);
        }
        return root;
    }
};

class Solution {
public:
    /**
     * @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.
     */
    TreeNode* insertNode(TreeNode* root, TreeNode* node) {
        // write your code here
        if(root == NULL)
            return node;
        TreeNode *cur = root;
        TreeNode *pre = root;
        while(cur != NULL) {//找到node所在那个叶子
            if(cur->val < node->val) {
                pre = cur;
                cur = cur->right;
            } else if(cur->val > node->val) {
                pre = cur;
                cur = cur->left;
            } else
                break;
        }
        if(pre->val > node->val)
            pre->left = node;
        if(pre->val < node->val)
            pre->right = node;
        return root;
    }
};