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(root==null){return0;}// 当前节点值小于low，左子树都不在范围内，只遍历右子树if(root.val<low){returnrangeSumBST(root.right,low,high);}// 当前节点值大于high，右子树都不在范围内，只遍历左子树if(root.val>high){returnrangeSumBST(root.left,low,high);}// 当前节点值在范围内，累加当前值 + 左右子树的结果returnroot.val+rangeSumBST(root.left,low,high)+rangeSumBST(root.right,low,high);}}方法二：迭代
classSolution{/** * 使用显式栈避免递归 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){if(root==null){return0;}Stack<TreeNode>stack=newStack<>();stack.push(root);intsum=0;while(!stack.isEmpty()){TreeNodecurrent=stack.pop();if(current==null){continue;}// 当前节点值在范围内if(current.val>=low&¤t.val<=high){sum+=current.val;// 左右子树都可能有符合条件的节点stack.push(current.left);stack.push(current.right);}// 当前节点值小于low，只考虑右子树elseif(current.val<low){stack.push(current.right);}// 当前节点值大于high，只考虑左子树else{stack.push(current.left);}}returnsum;}}方法三：BFS层序遍历
classSolution{/** * 使用队列进行层序遍历 */publicintrangeSumBST(TreeNoderoot,intlow,inthigh){if(root==null){return0;}Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);intsum=0;while(!queue.isEmpty()){TreeNodecurrent=queue.poll();if(current.val>=low&¤t.val<=high){sum+=current.val;if(current.left!=null)queue.offer(current.left);if(current.right!=null)queue.offer(current.right);}elseif(current.val<low){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(root==null){return0;}intsum=0;if(root.val>=low&&root.val<=high){sum+=root.val;}// 无论当前值如何，都要遍历左右子树sum+=rangeSumBST(root.left,low,high);sum+=rangeSumBST(root.right,low,high);returnsum;}}算法分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O(n) 最坏, O(log n) 平均 | O(h) |
| 迭代 | O(n) 最坏, O(log n) 平均 | O(h) |
| BFS | O(n) 最坏, O(log n) 平均 | O(w) |
| 无剪枝递归 | O(n) | O(h) |
算法过程
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
root.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 = 10
10 ∈ [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){Solutionsolution=newSolution();// 创建树节点TreeNodecreateNode(intval){returnnewTreeNode(val);}// 测试用例1：标准示例TreeNoderoot1=newTreeNode(10);root1.left=newTreeNode(5);root1.right=newTreeNode(15);root1.left.left=newTreeNode(3);root1.left.right=newTreeNode(7);root1.right.right=newTreeNode(18);System.out.println("Test 1: "+solution.rangeSumBST(root1,7,15));// 32// 测试用例2：另一个标准示例TreeNoderoot2=newTreeNode(10);root2.left=newTreeNode(5);root2.right=newTreeNode(15);root2.left.left=newTreeNode(3);root2.left.right=newTreeNode(7);root2.right.left=newTreeNode(13);root2.right.right=newTreeNode(18);root2.left.left.left=newTreeNode(1);root2.left.right.left=newTreeNode(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：单节点在范围内TreeNoderoot4=newTreeNode(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：所有节点都在范围内TreeNoderoot6=newTreeNode(5);root6.left=newTreeNode(3);root6.right=newTreeNode(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：边界值TreeNoderoot8=newTreeNode(10);root8.left=newTreeNode(5);root8.right=newTreeNode(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
- 单节点
- 范围边界值
常见问题
- 为什么不用中序遍历？
- 中序遍历虽然能得到有序序列，但无法利用范围信息进行剪枝
)
)
)
