938. Range Sum of BST

,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        return dfs(root, low, high);
    }

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

        int sum = 0;
        sum += dfs(node.left, low, high);
        if (node.val >= low && node.val <= high) {
            sum += node.val;
        }
        sum += dfs(node.right, low, high);
        return sum;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }

        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}

References

938. Range Sum of BST