# LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

### 题目:

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

```给定二叉搜索树:

4
/ \
2   7
/ \
1   3

```

```         4
/   \
2     7
/ \   /
1   3 5
```

```         5
/   \
2     7
/ \
1   3
\
4
```

### 解题思路:

1. 根据节点值与目标节点值的关系，搜索左子树或右子树；
2. 如果目标值小于节点的值，则继续在左子树中搜索;
3. 如果目标值大于节点的值，则继续在右子树中搜索。
4. 重复步骤 1 直到到达外部节点；
5. 根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。

### 递归法:

Java:

```class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null)
return new TreeNode(val);
if (val > root.val)
root.right = insertIntoBST(root.right, val);
else
root.right = insertIntoBST(root.right, val);
return root;
}
}
```

Python:

```class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return TreeNode(val)
if val > root.val:
root.right = self.insertIntoBST(root.right, val)
else:
root.left = self.insertIntoBST(root.left, val)
return root
```

Golang:

```func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
t := new(TreeNode)
t.Val = val
return t
}
if val > root.Val {
root.Right = insertIntoBST(root.Right, val)
} else {
root.Left = insertIntoBST(root.Left, val)
}
return root
}
```

### 迭代法:

Java:

```class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode node = root;
while (node != null) {
if (val > node.val) {
if (node.right == null) {
node.right = new TreeNode(val);
return root;
} else
node = node.right;
} else {
if (node.left == null) {
node.left = new TreeNode(val);
return root;
} else
node = node.left;
}
}
return new TreeNode(val);
}
}
```

Python:

```class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
node = root
while node:
if val > node.val:
if not node.right:
node.right = TreeNode(val)
return root
else:
node = node.right
else:
if not node.left:
node.left = TreeNode(val)
return root
else:
node = node.left
return TreeNode(val)
```

Golang:

```func insertIntoBST(root *TreeNode, val int) *TreeNode {
t := new(TreeNode)
t.Val = val
node := root
for node != nil {
if val > node.Val {
if node.Right == nil {
node.Right = t
return root
} else {
node = node.Right
}
} else {
if node.Left == nil {
node.Left = t
return root
} else {
node = node.Left
}
}
}
return t
}```

0 条评论

• ### 【leetcode刷题】T154-二叉搜索树中的插入操作

https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

• ### LeetCode - 二叉搜索树中的插入操作

原题地址：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

• ### LeetCode 701 Insert into a Binary Search Tree

因为是二叉搜索树，所以依次判断新值与每个节点的大小即可，大于当前节点，则判断此节点的右节点与新节点。小于当前节点，则判断此节点的左节点与新节点，直到子节点为空，...

• ### Js算法与数据结构拾萃（4）：二叉树

因此只要答对这道题，你就可以超越世界级大牛，问鼎码林之巅（逃） 导读： •二叉树知识重点•二叉树深度不一，因此天生适用递归，因此可用递归处理•判断两树相等•翻转...

• ### LeetCode通关：连刷三十九道二叉树，刷疯了！

大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的...

• ### LeetCode 701. 二叉搜索树中的插入操作（二叉查找树/插入）

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

• ### LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

• ### ​LeetCode刷题实战449：序列化和反序列化二叉搜索树

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 纸上谈兵: AVL树

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！ 二叉搜索树的深度与搜索效率 我们在树, 二...

• ### 48 Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted int...

• ### 二叉树问题（三）-LeetCode 669、951、662、199、538、236（中序，层次遍历）

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果...

• ### 纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树： ? 树有多个节点(node)，用以储存元素。某些节点之间存在...

• ### 【PAT甲级】Is It a Binary Search Tree

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### ​LeetCode刷题实战98：验证二叉搜索树

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### LeetCode - 二叉搜索树中的搜索

原题地址：https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

• ### LintCode 在二叉查找树中插入节点题目分析

给定一棵二叉查找树和一个新的树节点，将节点插入到树中。 你需要保证该树仍然是一棵二叉查找树。

• ### leetcode树之二叉搜索树的最近公共祖先

这里采用递归的思路，并利用二叉搜索树的特性来解题；针对root.val大于p.val及q.val的递归执行lowestCommonAncestor(root.l...

• ### 二叉树-LeetCode 235、236、226、230（中序，LCA，DFS）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 ...