【二叉树】二叉搜索树中的插入操作

解题思路：递归解决

递归结束条件：传入结点为叶子结点或对应的边为空，若val小于叶子结点val值，将其变为叶子结点左孩子，否则变为右孩子

1.若val大于根节点，传入右孩子进入函数

2.否则传入左孩子进入函数

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    if(!root) {
        return newNode;
    }
    if(val > root->val) {
        if(!root->right)
            root->right = newNode;
        else
            insertIntoBST(root->right, val);
    }
    else if(val < root->val) {
        if(!root->left)
            root->left = newNode;
        else
            insertIntoBST(root->left, val);
    }
    return root;
}

算法优化：函数返回新创建的结点

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
	if(!root) {
		struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
		return newNode;
	}
	if(val > root->val)
		root->right = insertIntoBST(root->right, val);
	else if(val < root->val)
		root->left = insertIntoBST(root->left, val);
	return root;
}

解题思路：递归解决

1.如果传入本来的二叉树不存在，创建新结点，返回该结点

2.设立两个结点，一个父亲结点parent，一个记录当前结点current。当current不为NULL时，判断val与current->val的值，调整，直到current为NULL为止

3.这时parent记录的是该被新结点插入的父亲结点。判断val与父亲结点的值然后再进行插入即可

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    if(!root) {
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        newNode->val = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    struct TreeNode* parent = root;
    struct TreeNode* current = root;
    while(current) {
        parent = current;
        if(val > current->val)
            current = current->right;
        else if(val < current->val)
            current = current->left;
    }

    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;

    if(val > parent->val)
        parent->right = newNode;
    else
        parent->left = newNode;
    return root;
}