LeetCode 701. 二叉搜索树中的插入操作

Categories:

题目描述
思路分析
1. 解法一：递归插入（推荐）
相似题目

题目描述

✅ 701. 二叉搜索树中的插入操作

思路分析

解法一：递归插入（推荐）

核心思路：

BST 的性质：左子树 < 根 < 右子树。

递归比较值大小，向左或向右子树插入。

当遇到空节点时创建新节点返回。

复杂度分析：

时间复杂度：O(h)，其中 h 为树高。

空间复杂度：O(h)，递归栈开销。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            // 插入到左子树
            root.left = insertIntoBST(root.left, val);
        } else {
            // 插入到右子树
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if val < root.Val {
        // 插入到左子树
        root.Left = insertIntoBST(root.Left, val)
    } else {
        // 插入到右子树
        root.Right = insertIntoBST(root.Right, val)
    }

    return root
}

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	BST
450. 删除二叉搜索树中的节点	中等	BST
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第K小的元素	中等	BST
530. 二叉搜索树的最小绝对差	简单	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/76017778