【Day-36慢就是快】代码随想录-二叉树-二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

思路

可以不用考虑题目中提示所说的改变树的结构的插入方式。

只需要按照二叉搜索树的规则去遍历，然后遇到空节点插入节点就可以了。

递归

1. 确定递归参数和返回值

参数就是传入根节点和插入节点的数值，添加当前节点的返回值可以实现新加入节点与其父节点的赋值绑定操作。

2. 终止条件

遍历的节点为空时，就是找到了插入节点的位置，并把插入的节点返回。

if (root == NULL) {
    TreeNode* node = new TreeNode(val);
    return node;
}

3. 单层递归的逻辑

搜索树是有方向的，根据插入元素的数值决定递归的方向。

if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;

这里用root->left接收返回值，同时也实现了当插入新节点后，与其父节点绑定的过程。

整体代码：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        TreeNode* cur = root;
        TreeNode* parent = root;//记录上一个节点，否则无法赋值新节点
        while(cur != NULL){
            parent = cur;
            if(cur->val > val) cur = cur->left;
            else cur = cur->right;
        }
        TreeNode* node = new TreeNode(val);
        if(val < parent->val) parent->left = node; //绑定父节点
        else parent->right = node; 
        return root;
    }
};