Leetcode-938 二叉搜索树的范围和

发表于 | 分类于

题目

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

示例 1：

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

示例 2：

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

提示：

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31。

思路一

直接遍历整个二叉树, 寻找大于等于L和小于等于R的结点的总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        return cntBSt(root, L, R);
    }

    int cntBSt(TreeNode root, int L, int R) {
        if (root == null) return 0;
        int result;
        if (root.val < L || root.val > R) result = 0;
        else result = root.val;
        result += cntBSt(root.left, L, R);
        result += cntBSt(root.right, L, R);
        return result;
    }
}

思路二

对上面的方法进行优化, 因为给定的树是二叉搜索树, 所以

  • 当结点小于L时, 只搜索该结点的右子树(左子树均小于L)
  • 当结点大于R时, 只搜索该结点的左子树(右子树均大于R)

换句话说

  • 只有结点大于L时, 才搜索左子树
  • 只有结点小于R时, 才搜索右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        return cntBSt(root, L, R);
    }

    int cntBSt(TreeNode root, int L, int R) {
        if (root == null) return 0;
        int result;
        if (root.val < L || root.val > R) result = 0;
        else result = root.val;
        if (root.val > L) result += cntBSt(root.left, L, R);  // val大于L才能进行搜索左子树
        if (root.val < R) result += cntBSt(root.right, L, R); // val小于R才能进行搜索右子树
        return result;
    }
}