分析

• 本题的考点：树的遍历。

• 本题只需要在二叉树的中序遍历过程中判断节点的值是否在[low, high]之间即可，如果在[low, high]之间，答案加上该节点的值。

• 关于树的遍历可以参考：树的遍历（二叉树、N叉树）。

• 可是使用非递归或者递归算法，这里用C++演示非递归算法，Java演示递归算法。

代码

• C++

class Solution {
public:
    int rangeSumBST(TreeNode *root, int low, int high) {

        int res = 0;
        stack<TreeNode *> stk;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top(); stk.pop();
            if (root->val >= low && root->val <= high) res += root->val;
            root = root->right;
        }
        return res;
    }
};

• Java

class Solution {

    int ans = 0;

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

    private void dfs(TreeNode root, int l, int r) {
        if (root == null) return;
        dfs(root.left, l, r);
        if (root.val >= l && root.val <= r) ans += root.val;
        dfs(root.right, l, r);
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为树中节点数。

• 空间复杂度：$O(n)$。