刷代码随想录有感（60）：二叉搜索树的插入操作

2024-05-09 14:25
算法
20人已看

题干：

代码：

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

解释：return newNode表示向上一层递归返回插入节点，给谁呢，谁来接住呢？是给下面写的“连接操作”的，root->left = ... 以及root->right = ...连接的对象就是newNode。

另外，题干看似复杂，可二叉搜索树的插入操作根本不涉及到结构调整，只需要将需要插入的节点插到叶子区域就可以了。