个人主页北极的代码欢迎来访作者简介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就把新节点放在那里具体例子假设现在有这样一棵树text4 / \ 2 7 / \ 1 3我们要插入5从根节点4开始5 4所以去右边来到75 7所以去左边7的左孩子是null找到位置了把新节点5放在这里结果变成text4 / \ 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小水一篇本来是打算每天两题但现在时间晚了肚子有点饿吃东西了所以就写了一题明天补回来哈哈。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】一篇搞懂-＞701.二叉搜索树的插入操作
个人主页北极的代码欢迎来访作者简介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就把新节点放在那里具体例子假设现在有这样一棵树text4 / \ 2 7 / \ 1 3我们要插入5从根节点4开始5 4所以去右边来到75 7所以去左边7的左孩子是null找到位置了把新节点5放在这里结果变成text4 / \ 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小水一篇本来是打算每天两题但现在时间晚了肚子有点饿吃东西了所以就写了一题明天补回来哈哈。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
