企业官网建设流程全解析

做调查问卷网站,苏州工业园区图片,wordpress页面显示摘要,动画设计师招聘938. 二叉搜索树的范围和 问题描述 给定二叉搜索树的根节点 root#xff0c;以及两个整数 low 和 high#xff0c;返回所有节点值在范围 [low, high] 内的节点值之和。 二叉搜索树#xff1a; 对于任意节点#xff0c;左子树的所有节点值都小于该节点值右子树的所有节点值都…938. 二叉搜索树的范围和问题描述给定二叉搜索树的根节点root以及两个整数low和high返回所有节点值在范围[low, high]内的节点值之和。二叉搜索树对于任意节点左子树的所有节点值都小于该节点值右子树的所有节点值都大于该节点值左右子树也都是二叉搜索树示例输入: root [10,5,15,3,7,null,18], low 7, high 15 输出: 32 解释: 节点值在[7,15]范围内的有: 7, 10, 15和为32。 输入: root [10,5,15,3,7,13,18,1,null,6], low 6, high 10 输出: 23 解释: 节点值在[6,10]范围内的有: 6, 7, 10和为23。算法思路核心思想如果当前节点值小于low则左子树所有节点都不在范围内只需遍历右子树如果当前节点值大于high则右子树所有节点都不在范围内只需遍历左子树如果当前节点值在范围内则累加该节点值并递归遍历左右子树代码实现方法一递归/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{/** * 计算二叉搜索树中范围[low, high]内节点值的和 * * param root 二叉搜索树的根节点 * param low 范围下界包含 * param high 范围上界包含 * return 范围内节点值的和 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){// 基础情况空节点if(rootnull){return0;}// 当前节点值小于low左子树都不在范围内只遍历右子树if(root.vallow){returnrangeSumBST(root.right,low,high);}// 当前节点值大于high右子树都不在范围内只遍历左子树if(root.valhigh){returnrangeSumBST(root.left,low,high);}// 当前节点值在范围内累加当前值 左右子树的结果returnroot.valrangeSumBST(root.left,low,high)rangeSumBST(root.right,low,high);}}方法二迭代classSolution{/** * 使用显式栈避免递归 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){if(rootnull){return0;}StackTreeNodestacknewStack();stack.push(root);intsum0;while(!stack.isEmpty()){TreeNodecurrentstack.pop();if(currentnull){continue;}// 当前节点值在范围内if(current.vallowcurrent.valhigh){sumcurrent.val;// 左右子树都可能有符合条件的节点stack.push(current.left);stack.push(current.right);}// 当前节点值小于low只考虑右子树elseif(current.vallow){stack.push(current.right);}// 当前节点值大于high只考虑左子树else{stack.push(current.left);}}returnsum;}}方法三BFS层序遍历classSolution{/** * 使用队列进行层序遍历 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){if(rootnull){return0;}QueueTreeNodequeuenewLinkedList();queue.offer(root);intsum0;while(!queue.isEmpty()){TreeNodecurrentqueue.poll();if(current.vallowcurrent.valhigh){sumcurrent.val;if(current.left!null)queue.offer(current.left);if(current.right!null)queue.offer(current.right);}elseif(current.vallow){if(current.right!null)queue.offer(current.right);}else{// current.val highif(current.left!null)queue.offer(current.left);}}returnsum;}}方法四无剪枝的递归classSolution{/** * 简单递归 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){if(rootnull){return0;}intsum0;if(root.vallowroot.valhigh){sumroot.val;}// 无论当前值如何都要遍历左右子树sumrangeSumBST(root.left,low,high);sumrangeSumBST(root.right,low,high);returnsum;}}算法分析方法时间复杂度空间复杂度递归O(n) 最坏, O(log n) 平均O(h)迭代O(n) 最坏, O(log n) 平均O(h)BFSO(n) 最坏, O(log n) 平均O(w)无剪枝递归O(n)O(h)算法过程输入root [10,5,15,3,7,null,18], low 7, high 15root.val 10∈ [7,15] → 累加10递归左右子树左子树(5)5 7→ 只遍历右子树(7)7 ∈ [7,15]→ 累加7左右子树为空右子树(15)15 ∈ [7,15]→ 累加15递归左右子树左子树为空右子树(18)18 15→ 只遍历左子树为空总和 10 7 15 32输入root [10,5,15,3,7,13,18,1,null,6], low 6, high 1010 ∈ [6,10]→ 累加10左子树(5)5 6→ 只遍历右子树(7)7 ∈ [6,10]→ 累加7左子树(6)6 ∈ [6,10]→ 累加6右子树(15)15 10→ 只遍历左子树(13)13 10→ 只遍历左子树为空总和 10 7 6 23测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 创建树节点TreeNodecreateNode(intval){returnnewTreeNode(val);}// 测试用例1标准示例TreeNoderoot1newTreeNode(10);root1.leftnewTreeNode(5);root1.rightnewTreeNode(15);root1.left.leftnewTreeNode(3);root1.left.rightnewTreeNode(7);root1.right.rightnewTreeNode(18);System.out.println(Test 1: solution.rangeSumBST(root1,7,15));// 32// 测试用例2另一个标准示例TreeNoderoot2newTreeNode(10);root2.leftnewTreeNode(5);root2.rightnewTreeNode(15);root2.left.leftnewTreeNode(3);root2.left.rightnewTreeNode(7);root2.right.leftnewTreeNode(13);root2.right.rightnewTreeNode(18);root2.left.left.leftnewTreeNode(1);root2.left.right.leftnewTreeNode(6);System.out.println(Test 2: solution.rangeSumBST(root2,6,10));// 23// 测试用例3空树System.out.println(Test 3: solution.rangeSumBST(null,1,10));// 0// 测试用例4单节点在范围内TreeNoderoot4newTreeNode(5);System.out.println(Test 4: solution.rangeSumBST(root4,5,5));// 5// 测试用例5单节点不在范围内System.out.println(Test 5: solution.rangeSumBST(root4,6,10));// 0// 测试用例6所有节点都在范围内TreeNoderoot6newTreeNode(5);root6.leftnewTreeNode(3);root6.rightnewTreeNode(7);System.out.println(Test 6: solution.rangeSumBST(root6,1,10));// 15// 测试用例7所有节点都不在范围内System.out.println(Test 7: solution.rangeSumBST(root6,8,10));// 0// 测试用例8边界值TreeNoderoot8newTreeNode(10);root8.leftnewTreeNode(5);root8.rightnewTreeNode(15);System.out.println(Test 8: solution.rangeSumBST(root8,10,10));// 10System.out.println(Test 9: solution.rangeSumBST(root8,5,15));// 30// 测试用例9大范围System.out.println(Test 10: solution.rangeSumBST(root8,1,100));// 30}关键点边界处理空树返回0单节点范围边界值常见问题为什么不用中序遍历中序遍历虽然能得到有序序列但无法利用范围信息进行剪枝