算法题 二叉搜索树中的插入操作
二叉搜索树中的插入操作
问题描述
给定二叉搜索树（BST）的根节点root和要插入树中的值val，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。
输入数据保证：新值和原始二叉搜索树中的任意节点值都不同。
注意：可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
二叉搜索树：
- 节点的左子树只包含小于当前节点的数
- 节点的右子树只包含大于当前节点的数
- 所有左子树和右子树自身也必须是二叉搜索树
示例：
输入: root = [4,2,7,1,3], val = 5 输出: [4,2,7,1,3,5] 解释: BST结构如下： 4 / \ 2 7 / \ / 1 3 5算法思路
递归：
- 基础情况：如果当前节点为空，创建新节点并返回
- 递归情况：
- 如果插入值小于当前节点值 → 递归插入到左子树
- 如果插入值大于当前节点值 → 递归插入到右子树
- 返回根节点：递归完成后返回原根节点（因为插入不会改变根节点）
迭代：
- 特殊情况：如果原树为空，直接返回新节点
- 找到插入位置：
- 从根节点开始遍历
- 根据BST移动到合适的叶子节点位置
- 执行插入：在找到的空位置创建新节点
关键：
- BST插入总是在叶子节点位置（或空树的根位置）
- 插入操作不会改变原有BST的结构，只增加一个叶子节点
- 保证插入值与所有现有值不同，无需处理重复值
代码实现
方法一：递归
// Definition for a binary tree node.classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}classSolution{/** * 在二叉搜索树中插入新值 * 使用递归，代码简洁 * * @param root BST的根节点 * @param val 要插入的值 * @return 插入后BST的根节点 */publicTreeNodeinsertIntoBST(TreeNoderoot,intval){// 基础情况：找到插入位置（空节点）if(root==null){returnnewTreeNode(val);}// 根据BST决定插入方向if(val<root.val){// 插入值小于当前节点值，在左子树中插入root.left=insertIntoBST(root.left,val);}else{// 插入值大于当前节点值，在右子树中插入root.right=insertIntoBST(root.right,val);}// 返回原根节点（根节点不会改变）returnroot;}}方法二：迭代
classSolution{/** * 在二叉搜索树中插入新值 * 使用迭代，空间复杂度更优 * * @param root BST的根节点 * @param val 要插入的值 * @return 插入后BST的根节点 */publicTreeNodeinsertIntoBST(TreeNoderoot,intval){// 特殊情况：空树if(root==null){returnnewTreeNode(val);}TreeNodecurrent=root;TreeNodeparent=null;// 找到插入位置的父节点while(current!=null){parent=current;if(val<current.val){current=current.left;}else{current=current.right;}}// 在父节点的适当位置插入新节点if(val<parent.val){parent.left=newTreeNode(val);}else{parent.right=newTreeNode(val);}returnroot;}}算法分析
- 时间复杂度：
- 平均情况：O(log N)，N为节点数（平衡BST）
- 最坏情况：O(N)，退化为链表的情况
- 空间复杂度：
- 递归：O(H)，H为树的高度（递归调用栈）
- 迭代：O(1)，只使用常数额外空间
算法过程
root = [4,2,7,1,3], val = 5
递归插入：
- 当前节点4，val=5 > 4 → 在右子树插入
- 当前节点7，val=5 < 7 → 在左子树插入
- 当前节点null → 创建新节点5并返回
- 节点7的左子节点指向新节点5
- 返回原根节点4
最终树结构：
4 / \ 2 7 / \ / 1 3 5插入位置：
- 5 > 4，所以应该在4的右子树
- 5 < 7，所以应该在7的左子树
- 7的左子树为空，所以5成为7的左子节点
测试用例
publicclassTestInsertIntoBST{// 构建测试用的二叉搜索树privatestaticTreeNodebuildBST(Integer[]values){if(values==null||values.length==0||values[0]==null){returnnull;}TreeNoderoot=newTreeNode(values[0]);for(inti=1;i<values.length;i++){if(values[i]!=null){insert(root,values[i]);}}returnroot;}privatestaticvoidinsert(TreeNoderoot,intval){if(val<root.val){if(root.left==null){root.left=newTreeNode(val);}else{insert(root.left,val);}}else{if(root.right==null){root.right=newTreeNode(val);}else{insert(root.right,val);}}}// 序列化树用于输出privatestaticList<Integer>inorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();inorderHelper(root,result);returnresult;}privatestaticvoidinorderHelper(TreeNodenode,List<Integer>result){if(node!=null){inorderHelper(node.left,result);result.add(node.val);inorderHelper(node.right,result);}}// 层次遍历序列化privatestaticList<Integer>levelOrderSerialize(TreeNoderoot){List<Integer>result=newArrayList<>();if(root==null){returnresult;}Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecurrent=queue.poll();if(current==null){result.add(null);}else{result.add(current.val);queue.offer(current.left);queue.offer(current.right);}}// 移除末尾的null值while(!result.isEmpty()&&result.get(result.size()-1)==null){result.remove(result.size()-1);}returnresult;}publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例 - 插入到右子树TreeNoderoot1=buildBST(newInteger[]{4,2,7,1,3});TreeNoderesult1=solution.insertIntoBST(root1,5);System.out.println("Test 1 (level order): "+levelOrderSerialize(result1));// [4,2,7,1,3,5]System.out.println("Test 1 (inorder): "+inorderTraversal(result1));// [1,2,3,4,5,7]// 测试用例2：插入到左子树最左侧TreeNoderoot2=buildBST(newInteger[]{4,2,7,1,3});TreeNoderesult2=solution.insertIntoBST(root2,0);System.out.println("Test 2 (level order): "+levelOrderSerialize(result2));// [4,2,7,1,3,null,null,0]System.out.println("Test 2 (inorder): "+inorderTraversal(result2));// [0,1,2,3,4,7]// 测试用例3：空树插入TreeNoderesult3=solution.insertIntoBST(null,1);System.out.println("Test 3 (level order): "+levelOrderSerialize(result3));// [1]System.out.println("Test 3 (inorder): "+inorderTraversal(result3));// [1]// 测试用例4：单节点插入（更大值）TreeNoderoot4=buildBST(newInteger[]{5});TreeNoderesult4=solution.insertIntoBST(root4,10);System.out.println("Test 4 (level order): "+levelOrderSerialize(result4));// [5,null,10]System.out.println("Test 4 (inorder): "+inorderTraversal(result4));// [5,10]// 测试用例5：单节点插入（更小值）TreeNoderoot5=buildBST(newInteger[]{5});TreeNoderesult5=solution.insertIntoBST(root5,2);System.out.println("Test 5 (level order): "+levelOrderSerialize(result5));// [5,2]System.out.println("Test 5 (inorder): "+inorderTraversal(result5));// [2,5]// 测试用例6：插入到复杂BSTTreeNoderoot6=buildBST(newInteger[]{10,5,15,3,7,12,18,1,4,6,8});TreeNoderesult6=solution.insertIntoBST(root6,11);System.out.println("Test 6 (level order): "+levelOrderSerialize(result6));// [...,11,...]System.out.println("Test 6 (inorder size): "+inorderTraversal(result6).size());// 12// 测试用例7：插入最大值TreeNoderoot7=buildBST(newInteger[]{5,3,8,2,4,7,9});TreeNoderesult7=solution.insertIntoBST(root7,15);List<Integer>inorder7=inorderTraversal(result7);System.out.println("Test 7 (max value): "+inorder7.get(inorder7.size()-1));// 15// 测试用例8：插入最小值TreeNoderoot8=buildBST(newInteger[]{5,3,8,2,4,7,9});TreeNoderesult8=solution.insertIntoBST(root8,0);List<Integer>inorder8=inorderTraversal(result8);System.out.println("Test 8 (min value): "+inorder8.get(0));// 0// 测试用例9：深度插入TreeNoderoot9=buildBST(newInteger[]{100,50,150,25,75,125,175});TreeNoderesult9=solution.insertIntoBST(root9,12);System.out.println("Test 9 (deep insert): "+levelOrderSerialize(result9).size());// 8 nodes}}关键点
BST插入位置：
- 插入位置是唯一的（因为值不重复）
- 总是在叶子节点位置插入
- 保证插入后仍满足BST
递归返回值：
- 递归函数返回插入后子树的根节点
- 父节点用返回值更新相应的子节点指针
- 最终返回原根节点
边界情况处理：
- 空树：直接返回新节点
- 单节点树：根据值大小决定左右插入
常见问题
为什么插入位置是唯一的？
- BST中每个值都有确定的位置，新值必须插入到保持BST的唯一位置。
插入操作会改变树的平衡性？
- 普通的BST插入不保证平衡性。如果需要保持平衡，应该使用AVL树或红黑树。