网站官网认证怎么做关键字搜索引擎

网站官网认证怎么做,关键字搜索引擎,网站设计方案范文,国外包装设计网站二叉搜索树中的插入操作 问题描述 给定二叉搜索树#xff08;BST#xff09;的根节点 root 和要插入树中的值 val#xff0c;将值插入二叉搜索树。返回插入后二叉搜索树的根节点。 输入数据保证#xff1a;新值和原始二叉搜索树中的任意节点值都不同。 注意#xff1a;可能…二叉搜索树中的插入操作问题描述给定二叉搜索树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.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}classSolution{/** * 在二叉搜索树中插入新值 * 使用递归代码简洁 * * param root BST的根节点 * param val 要插入的值 * return 插入后BST的根节点 */publicTreeNodeinsertIntoBST(TreeNoderoot,intval){// 基础情况找到插入位置空节点if(rootnull){returnnewTreeNode(val);}// 根据BST决定插入方向if(valroot.val){// 插入值小于当前节点值在左子树中插入root.leftinsertIntoBST(root.left,val);}else{// 插入值大于当前节点值在右子树中插入root.rightinsertIntoBST(root.right,val);}// 返回原根节点根节点不会改变returnroot;}}方法二迭代classSolution{/** * 在二叉搜索树中插入新值 * 使用迭代空间复杂度更优 * * param root BST的根节点 * param val 要插入的值 * return 插入后BST的根节点 */publicTreeNodeinsertIntoBST(TreeNoderoot,intval){// 特殊情况空树if(rootnull){returnnewTreeNode(val);}TreeNodecurrentroot;TreeNodeparentnull;// 找到插入位置的父节点while(current!null){parentcurrent;if(valcurrent.val){currentcurrent.left;}else{currentcurrent.right;}}// 在父节点的适当位置插入新节点if(valparent.val){parent.leftnewTreeNode(val);}else{parent.rightnewTreeNode(val);}returnroot;}}算法分析时间复杂度平均情况O(log N)N为节点数平衡BST最坏情况O(N)退化为链表的情况空间复杂度递归O(H)H为树的高度递归调用栈迭代O(1)只使用常数额外空间算法过程root [4,2,7,1,3], val 5递归插入当前节点4val5 4 → 在右子树插入当前节点7val5 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(valuesnull||values.length0||values[0]null){returnnull;}TreeNoderootnewTreeNode(values[0]);for(inti1;ivalues.length;i){if(values[i]!null){insert(root,values[i]);}}returnroot;}privatestaticvoidinsert(TreeNoderoot,intval){if(valroot.val){if(root.leftnull){root.leftnewTreeNode(val);}else{insert(root.left,val);}}else{if(root.rightnull){root.rightnewTreeNode(val);}else{insert(root.right,val);}}}// 序列化树用于输出privatestaticListIntegerinorderTraversal(TreeNoderoot){ListIntegerresultnewArrayList();inorderHelper(root,result);returnresult;}privatestaticvoidinorderHelper(TreeNodenode,ListIntegerresult){if(node!null){inorderHelper(node.left,result);result.add(node.val);inorderHelper(node.right,result);}}// 层次遍历序列化privatestaticListIntegerlevelOrderSerialize(TreeNoderoot){ListIntegerresultnewArrayList();if(rootnull){returnresult;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurrentqueue.poll();if(currentnull){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){SolutionsolutionnewSolution();// 测试用例1标准示例 - 插入到右子树TreeNoderoot1buildBST(newInteger[]{4,2,7,1,3});TreeNoderesult1solution.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插入到左子树最左侧TreeNoderoot2buildBST(newInteger[]{4,2,7,1,3});TreeNoderesult2solution.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空树插入TreeNoderesult3solution.insertIntoBST(null,1);System.out.println(Test 3 (level order): levelOrderSerialize(result3));// [1]System.out.println(Test 3 (inorder): inorderTraversal(result3));// [1]// 测试用例4单节点插入更大值TreeNoderoot4buildBST(newInteger[]{5});TreeNoderesult4solution.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单节点插入更小值TreeNoderoot5buildBST(newInteger[]{5});TreeNoderesult5solution.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插入到复杂BSTTreeNoderoot6buildBST(newInteger[]{10,5,15,3,7,12,18,1,4,6,8});TreeNoderesult6solution.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插入最大值TreeNoderoot7buildBST(newInteger[]{5,3,8,2,4,7,9});TreeNoderesult7solution.insertIntoBST(root7,15);ListIntegerinorder7inorderTraversal(result7);System.out.println(Test 7 (max value): inorder7.get(inorder7.size()-1));// 15// 测试用例8插入最小值TreeNoderoot8buildBST(newInteger[]{5,3,8,2,4,7,9});TreeNoderesult8solution.insertIntoBST(root8,0);ListIntegerinorder8inorderTraversal(result8);System.out.println(Test 8 (min value): inorder8.get(0));// 0// 测试用例9深度插入TreeNoderoot9buildBST(newInteger[]{100,50,150,25,75,125,175});TreeNoderesult9solution.insertIntoBST(root9,12);System.out.println(Test 9 (deep insert): levelOrderSerialize(result9).size());// 8 nodes}}关键点BST插入位置插入位置是唯一的因为值不重复总是在叶子节点位置插入保证插入后仍满足BST递归返回值递归函数返回插入后子树的根节点父节点用返回值更新相应的子节点指针最终返回原根节点边界情况处理空树直接返回新节点单节点树根据值大小决定左右插入常见问题为什么插入位置是唯一的BST中每个值都有确定的位置新值必须插入到保持BST的唯一位置。插入操作会改变树的平衡性普通的BST插入不保证平衡性。如果需要保持平衡应该使用AVL树或红黑树。