【原】545，二叉搜索树的范围和

数据结构和算法 2023-06-10 发布于上海

展开全文

Nothing is impossible.

没有什么是不可能的。

问题描述

给定二叉搜索树的根结点root，返回值位于范围[low, high]之间的所有结点的值的和。

示例 1：

输入：root = [10,5,15,3,7,null,18],
low = 7, high = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6],
low = 6, high = 10
输出：23

提示：

树中节点数目在范围 [1, 2 * 10^4] 内
1 <= Node.val <= 10^5
1 <= low <= high <= 10^5
所有Node.val互不相同

逐个遍历

我们遍历二叉树的每一个节点，判断他的值是否在[low, high]之间，如果在这个之间，我们就统计他们的和。

而遍历二叉树的方式有很多，前序，中序，后续，BFS，并且每种方式都有递归和非递归等多种实现方式，如果还嫌不够，还有Morris的前序，中序，后续。那这样写下来答案就比较多了。

关于二叉树的前中后，以及BFS遍历可以看下《373，数据结构-6,树》

关于二叉树的Morris遍历方式可以看下《488，二叉树的Morris中序和前序遍历》

解法比较多，这里就随便挑一个来写，比如二叉树的中序遍历递归写法如下

1public void inOrderTraversal(TreeNode node) {
2    if (node == null)
3        return;
4    inOrderTraversal(node.left);
5    System.out.println(node.val);
6    inOrderTraversal(node.right);
7}

我们来对他改造一下，遍历每个节点的时候判断他的值

 1int res = 0;
 2
 3public int rangeSumBST(TreeNode root, int low, int high) {
 4    inOrderTraversal(root, low, high);
 5    return res;
 6}
 7
 8public void inOrderTraversal(TreeNode node, int low, int high) {
 9    if (node == null)
10        return;
11    inOrderTraversal(node.left, low, high);
12    //如果当前节点的值在[low, high]之间，就累加
13    if (node.val >= low && node.val <= high)
14        res += node.val;
15    inOrderTraversal(node.right, low, high);
16}

代码优化

这题有个条件就是二搜索叉树，我们知道二叉搜索树的特点就是左子树的所有节点值都比当前节点值小，右子树的所有节点值都比当前节点值大，如果我们按照中序遍历的方式打印的话，就会发现打印的结果是升序排列的。

上面那种解法遍历每一个节点，虽然也能解决问题，但很效率不是最好的，对于二叉搜索树

如果当前节点小于low，那么他它的左子树的所有节点肯定也都小于low，我们没必要在遍历了，直接放弃
如果当前节点大于high，那么他的右子树的所有节点肯定也都大于high，也可以放弃

来看下代码

 1public int rangeSumBST(TreeNode root, int low, int high) {
 2    //递归边界条件判断
 3    if (root == null)
 4        return 0;
 5    //当前节点以及他的右子树的值都太大了，不要了
 6    if (root.val > high) {
 7        return rangeSumBST(root.left, low, high);
 8    }
 9    //当前节点以及他的左子树的值都太小了，也不要了
10    if (root.val < low) {
11        return rangeSumBST(root.right, low, high);
12    }
13    //如果当前节点值在[low, high]之间，就留下
14    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
15}