OJ lintcode 在二叉查找树中插入节点

给定一棵二叉查找树和一个新的树节点，将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。

image.png

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.
     */
     
     /*这里的pre 相当于是p 节点的父节点  */
    void  insert(TreeNode * p,TreeNode * pre,TreeNode * node){
        if(p==NULL){
            if(pre->val<node->val){
                pre->right=node;
            }
            else{
                pre->left=node;
            }
        }
        else{
            if(p->val<node->val){
                //node 大于
                insert(p->right,p,node);
            }
            else{
                insert(p->left,p,node);
            }
        }
    }
    TreeNode* insertNode(TreeNode* root, TreeNode* node) {
        // write your code here
        if(root==NULL){
            root=node;
            return root;
        }
        if(root->val<node->val){
            insert(root->right,root,node);
        }
        else{
            insert(root->left,root,node);
        }

        return root;
    }
};