LeetCode 701. Insert into a Binary Search Tree 题解
LeetCode 701. Insert into a Binary Search Tree 题解
题目描述
给定二叉搜索树（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]解题思路
方法一：递归
思路：
- 利用二叉搜索树的性质：左子树的所有节点值小于根节点的值，右子树的所有节点值大于根节点的值
- 递归地插入目标值：
- 如果当前节点为空，创建一个新节点并返回
- 如果当前节点的值大于目标值，递归插入到左子树
- 如果当前节点的值小于目标值，递归插入到右子树
- 返回根节点
复杂度分析：
- 时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，二叉搜索树退化为链表，时间复杂度为 O(n)。
- 空间复杂度：O(h)，递归调用的栈空间取决于二叉搜索树的高度。
方法二：迭代
思路：
- 使用迭代的方式，利用二叉搜索树的性质插入目标值
- 当当前节点不为空时：
- 如果当前节点的值大于目标值，移动到左子节点
- 如果当前节点的值小于目标值，移动到右子节点
- 当当前节点为空时，创建一个新节点并插入到父节点的相应位置
复杂度分析：
- 时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，二叉搜索树退化为链表，时间复杂度为 O(n)。
- 空间复杂度：O(1)，只需要常数级的额外空间。
代码实现
方法一：递归
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: # 递归终止条件：如果当前节点为空，创建一个新节点并返回 if not root: return TreeNode(val) # 如果当前节点的值大于目标值，递归插入到左子树 if root.val > val: root.left = self.insertIntoBST(root.left, val) # 如果当前节点的值小于目标值，递归插入到右子树 else: root.right = self.insertIntoBST(root.right, val) # 返回根节点 return root方法二：迭代
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: # 如果根节点为空，创建一个新节点并返回 if not root: return TreeNode(val) current = root parent = None # 找到插入位置 while current: parent = current if current.val > val: current = current.left else: current = current.right # 创建新节点并插入到父节点的相应位置 if parent.val > val: parent.left = TreeNode(val) else: parent.right = TreeNode(val) return root测试用例
测试用例 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]
总结
本题是二叉搜索树的经典问题，主要考察对二叉搜索树性质的理解和应用。通过使用递归或迭代，我们可以高效地在二叉搜索树中插入目标值。
递归的核心思想是：利用二叉搜索树的性质，递归地插入目标值。迭代的核心思想是：使用循环的方式，利用二叉搜索树的性质找到插入位置，然后创建新节点并插入。
在实际应用中，迭代方法通常更受欢迎，因为它的空间复杂度更低，而且避免了递归调用的栈开销。
这种方法不仅适用于二叉搜索树中的插入操作，还可以应用于许多其他需要在二叉搜索树中插入元素的场景。掌握这些方法，对于解决这类问题非常重要。