力扣701题：二叉搜索树插入操作 - 递归解法详解

内容简介

本文详细解析了力扣701题"二叉搜索树中的插入操作"的递归实现方法。通过遵循二叉搜索树的性质，展示了如何高效地在BST中插入新节点。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握BST操作的核心技巧。

算法思路

‌递归终止条件‌：当到达空节点时创建新节点

‌值比较‌：根据插入值与当前节点值的比较决定递归方向

‌递归插入‌：在左子树或右子树中继续寻找合适位置

‌保持BST性质‌：确保插入后仍满足左<根<右的性质

代码实现（带详细注释）

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 基本情况：如果当前节点为空，创建新节点并返回
        if(!root){
            root = new TreeNode(val);
            return root;
        }
        
        // 如果插入值小于当前节点值，递归插入左子树
        if(val < root->val){
            root->left = insertIntoBST(root->left, val);
        }
        // 如果插入值大于当前节点值，递归插入右子树
        else if(val > root->val){
            root->right = insertIntoBST(root->right, val);
        }
        
        // 返回当前(可能更新后的)根节点
        return root;
    }
};

复杂度分析

‌时间复杂度‌：O(h)，h为树的高度，最坏情况O(n)

‌空间复杂度‌：O(h)，递归栈空间取决于树的高度

优化方向

‌迭代解法‌：使用循环替代递归减少栈空间使用

‌平衡BST‌：插入后检查并保持树的平衡

‌批量插入‌：优化连续插入多个值的效率

总结

BST插入操作是理解二叉搜索树基础操作的关键，递归实现简洁明了地展现了BST的性质和操作逻辑。掌握这种解法有助于深入理解树结构的操作原理。