938. 二叉搜索树的范围和

题解:

二叉树中序遍历, 递加在 [L , R] 范围的元素即可。

思路一:

递归 代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
		int sum = 0;
    public int rangeSumBST(TreeNode root, int L, int R){
        if (root == null) return 0;

        rangeSumBST(root.left, L ,R);
        if (root.val >= L && root.val <= R){
            sum += root.val;
        }
        rangeSumBST(root.right,L,R);

        return sum;
    }
思路二:

迭代 代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 // 迭代
    public int rangeSumBST1(TreeNode root, int L, int R){
        if (root == null) return 0;

        // 保存最终结果
        int sum = 0;

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if (root.val >= L && root.val <= R){
                sum += root.val;
            }

            root = root.right;
        }

        return sum;
    }