938. Range Sum of BST

dfs inorder

time:O(n), space:O(1)

global variable

class Solution {
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        inorder(root, low, high);
        return sum;
    }
    
    private void inorder(TreeNode root, int low, int high) {
        if (root == null) {
            return;
        }
        rangeSumBST(root.left, low, high);
        if (root.val >= low && root.val <= high) {
            sum += root.val;
        }
        rangeSumBST(root.right, low, high);
    }
    
}

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        return dfs(root, low, high);
    }
    private int dfs(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        sum += dfs(root.left, low, high);
        if (root.val <= high && root.val >= low) {
            sum += root.val;
        }
        sum += dfs(root.right, low, high);
        return sum;
    }
}

divide and conquer

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) +
            (root.val >= low && root.val <= high ? root.val : 0);
    }
   
    
}

stack

class Solution {
    private Deque<TreeNode> stack;
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        stack = new ArrayDeque<>();
        findLeftMost(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val >= low && node.val <= high) {
                sum += node.val;
            }
            if (node.right != null) {
                findLeftMost(node.right);
            }
        }
        return sum;
    }
    private void findLeftMost(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}