938.二叉搜索树的范围和

链接：938.二叉搜索树的范围和
难度：Easy
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

题解 1 - java

• 编辑时间：2020-02-24
• 执行用时：10ms
• 内存消耗：47.5MB
• 编程语言：java
• 解法介绍：中序遍历后循环判断。

class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>(10000);
	public int rangeSumBST(TreeNode root, int L, int R) {
		inorder(root);
		int sum = 0;
		for (int i = 0, len = list.size(); i < len; i++) {
			if (list.get(i) < L)
				continue;
			else if (list.get(i) >= L && list.get(i) <= R)
				sum += list.get(i);
			else
				break;
		}
		return sum;
	}
	public void inorder(TreeNode node) {
		if (node.left != null)
			inorder(node.left);
		list.add(node.val);
		if (node.right != null)
			inorder(node.right);
	}
}

题解 2 - typescript

• 编辑时间：2021-04-27
• 执行用时：288ms
• 内存消耗：65.9MB
• 编程语言：typescript
• 解法介绍：递归判断。

function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
        let sum = 0;
        const sumNode = (node: TreeNode | null): void => {
          if (node === null) return;
          const val = node.val;
          if (val < low) sumNode(node.right);
          else if (val > high) sumNode(node.left);
          else {
            sum += val;
            sumNode(node.right);
            sumNode(node.left);
          }
        };
        sumNode(root);
        return sum;
      }}

题解 3 - python

• 编辑时间：2024-02-26
• 执行用时：98ms
• 内存消耗：24.04MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root: return 0
        if root.val < low: return self.rangeSumBST(root.right, low, high)
        if root.val > high: return self.rangeSumBST(root.left, low, high)
        return root.val + self.rangeSumBST(root.right, low, high) + self.rangeSumBST(root.left, low, high)