当前位置：首页 > news >正文

【LeetCode刷题日记】一篇搞懂-＞701.二叉搜索树的插入操作

news 2026/5/27 2:46:17

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，又到了我们每日的刷题环节，还有几题我们二叉树相关的章节就要学完了，后面的感觉更有意思点，贪心算法等等，看着挺新颖的。虽然是水了一篇，但是今天主要在看GitHub，看看有没有什么能做的东西。

摘要：

本文介绍了在二叉搜索树（BST）中插入新节点的两种方法。题目要求给定BST根节点和插入值，返回插入后的树结构。关键点在于利用BST特性：左子树值小于根节点，右子树值大于根节点。插入过程通过比较节点值决定向左或向右遍历，直到找到合适空位。
方法一采用递归实现，时间复杂度O(H)（H为树高），空间复杂度O(H)用于递归栈。方法二使用迭代方式，时间复杂度相同但空间优化至O(1)。两种方法都能正确处理空树情况，确保新节点插入后仍保持BST性质。文章通过具体示例（如插入值5到树[4,2,7,1,3]）演示了插入过程，并强调迭代法通过指针移动替代递归栈的优势。

题目背景：

给定二叉搜索树（BST）的根节点root和要插入树中的值value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
示例 1：
输入：root = [4,2,7,1,3], val = 5输出：[4,2,7,1,3,5]解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5输出：[4,2,7,1,3,5]
提示：
树中的节点数将在[0, 104]的范围内。
-108 <= Node.val <= 108
所有值Node.val是独一无二的。
-108 <= val <= 108
保证val在原始BST中不存在。

题目解析：

首先我们要知道：
二叉搜索树的性质：
左子树所有节点的值 < 根节点的值
右子树所有节点的值 > 根节点的值
左右子树也分别是二叉搜索树

因此插入操作的本质：找到适合插入的叶子节点位置

BST有一个重要规则：左边所有节点都比根小，右边所有节点都比根大。
所以插入的过程很简单：拿着要插入的值，从根节点开始，一路往下走：
如果比当前节点小，就去左边找位置
如果比当前节点大，就去右边找位置
直到遇到空位置（null），就把新节点放在那里

具体例子：

假设现在有这样一棵树：
text
4 / \ 2 7 / \ 1 3
我们要插入5：
从根节点4开始：5 > 4，所以去右边
来到7：5 < 7，所以去左边
7的左孩子是null，找到位置了！把新节点5放在这里
结果变成：
text
4 / \ 2 7 / \ / 1 3 5

两种实现方式

递归方式：写一个函数，不断调用自己往左或往右走，遇到空就创建新节点返回。代码很简洁，理解起来最直观。
迭代方式：用while循环代替递归，用一个指针不断往下移动，找到空位就插入。不需要额外的递归栈空间，性能更好。

递归法我们都很了解了，代码实现也很简单，这里重点说一下迭代法，毕竟代码看着有点多

迭代写法就是用循环代替递归，通过一个指针在树中移动，找到空位就插入。整个过程不需要函数调用自己，代码执行效率更高。

核心思路

想象你手里拿着一个新节点，从根节点开始往下走：

用current指针表示当前到达的节点
每次比较新值和current的值，决定向左走还是向右走
如果目标方向是空的，就把新节点放进去，结束
如果目标方向有节点，就移动指针到那个节点，继续循环

关键点

新插入的节点永远在叶子节点位置，不会改变原有节点的父子关系
题目已经保证新值和树里所有值都不同，所以不用担心相等的情况
树可能为空（root为null），这时候直接返回新节点作为根就行

题目答案：

方法一：递归实现

java class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { // 基础情况：如果当前节点为空，说明找到了插入位置，创建新节点 if (root == null) { return new TreeNode(val); } // 根据 BST 性质决定向左或向右递归 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(log n)，最坏 O(n)）
空间复杂度：O(H)，递归调用栈的深度

方法二：迭代实现

java class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { TreeNode newNode = new TreeNode(val); // 特殊情况：空树 if (root == null) { return newNode; } TreeNode current = root; while (true) { if (val < current.val) { // 向左走 if (current.left == null) { current.left = newNode; break; } else { current = current.left; } } else { // 向右走 if (current.right == null) { current.right = newNode; break; } else { current = current.right; } } } return root; } }

时间复杂度：O(H)
空间复杂度：O(1)，只使用了常数级额外空间

ps：小水一篇，本来是打算每天两题，但现在时间晚了肚子有点饿，吃东西了，所以就写了一题，明天补回来，哈哈。