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, val0, leftNone, rightNone): # 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, val0, leftNone, rightNone): # 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]总结本题是二叉搜索树的经典问题主要考察对二叉搜索树性质的理解和应用。通过使用递归或迭代我们可以高效地在二叉搜索树中插入目标值。递归的核心思想是利用二叉搜索树的性质递归地插入目标值。迭代的核心思想是使用循环的方式利用二叉搜索树的性质找到插入位置然后创建新节点并插入。在实际应用中迭代方法通常更受欢迎因为它的空间复杂度更低而且避免了递归调用的栈开销。这种方法不仅适用于二叉搜索树中的插入操作还可以应用于许多其他需要在二叉搜索树中插入元素的场景。掌握这些方法对于解决这类问题非常重要。