938. Range Sum of BST

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].



Example 1:


Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Example 2:


Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23


Constraints:

The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.

这题只要对树的遍历熟悉，就能做出来，一个深度优先遍历所有的节点就搞定了。

结合BST的定义，我们可以做一下剪枝判断。

class RangeSumOfBST : public Solution {
    public:
    void Execute() {

    }

    int dfs(TreeNode *node, int low, int high) {
        if (nullptr == node) {
            return 0;
        }

        int sum = 0;
        if (node->val >= low && node->val <= high) {
            sum += node->val;
        }
        // Left children
        if (node->val >= low) {
            sum += dfs(node->left, low, high);
        }
        if (node->val <= high) {
            sum += dfs(node->right, low, high);
        }

        return sum;
    }

    int rangeSumBST(TreeNode* root, int low, int high) {
        return dfs(root, low, high);
    }
};