938. 二叉搜索树的范围和

Posted on | In
Words count in article: 383 | Reading time ≈ 1

题目

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

示例1：

1
2
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例2：

1
2
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

提示：

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31。

解法

参考这里

解法一：

深度优先搜索-递归实现

我们对树进行深度优先搜索，对于当前节点 node，如果 node.val 小于等于 L，那么只需要继续搜索它的右子树；如果 node.val 大于等于 R，那么只需要继续搜索它的左子树；如果 node.val 在区间 (L, R) 中，则需要搜索它的所有子树。

JAVA

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

	public int dfs(TreeNode node, int L, int R) {
		int sum = 0;
		if (node != null) {
			if (L <= node.val && node.val <= R) {
				sum += node.val;
			}
			if (L < node.val) {
				sum += dfs(node.left, L, R);
			}
			if (node.val < R) {
				sum += dfs(node.right, L, R);
			}
		}
		return sum;
	}

解法二：

深度优先搜索-迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int rangeSumBST(TreeNode root, int L, int R) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }
0%