What is the primary approach for solving the Range Sum of BST problem?

The primary approach is to perform a DFS traversal while leveraging the BST properties to prune unnecessary branches and compute the sum of nodes within the given range.

How do we handle large trees with deep recursion in this problem?

You can implement the solution iteratively using a stack to avoid deep recursion and prevent stack overflow issues in large trees.

Can we solve the Range Sum of BST problem using a BFS approach?

While DFS is the most common approach, BFS can also be used, especially in situations where level-wise processing of the tree is needed.

What are some common pitfalls when solving Range Sum of BST?

Common pitfalls include failing to properly prune unnecessary branches, incorrectly handling range bounds, and facing stack overflow issues due to deep recursion.

How can GhostInterview help with this problem?

GhostInterview guides users through optimizing the traversal, reinforcing understanding of pruning, and ensuring efficient implementation with both recursive and iterative solutions.

#938

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉搜索树的范围和

给定二叉搜索树的根结点 root ，返回值位于范围 [low, high] 之间的所有结点的值的和。示例 1：输入： root = [10,5,15,3,7,null,18], low = 7, high = 15 输出： 32 示例 2：输入： root = [10,5,15,3,7,13,…

树深度优先搜索二叉搜索树二叉树

题目描述

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：

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

示例 2：

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

提示：

树中节点数目在范围 [1, 2 * 10⁴] 内
1 <= Node.val <= 10⁵
1 <= low <= high <= 10⁵
所有 Node.val 互不相同

lightbulb

解题思路

方法一：DFS

我们设计一个函数 $dfs(root)$ ，表示求以 $root$ 为根的子树中，值位于范围 $[low, high]$ 之间的所有结点的值的和。那么答案就是 $dfs(root)$ 。

函数 $dfs(root)$ 的执行逻辑如下：

如果 $root$ 为空，返回 $0$ 。
如果 $root$ 的值 $x$ 在范围 $[low, high]$ 之间，那么函数 $dfs(root)$ 的初始答案就是 $x$ ，否则为 $0$ 。
如果 $x > low$ ，说明 $root$ 的左子树中可能有值在范围 $[low, high]$ 之间的结点，所以我们需要递归调用 $dfs(root.left)$ ，并将结果加到答案上。
如果 $x < high$ ，说明 $root$ 的右子树中可能有值在范围 $[low, high]$ 之间的结点，所以我们需要递归调用 $dfs(root.right)$ ，并将结果加到答案上。
最后返回答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉搜索树的结点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            x = root.val
            ans = x if low <= x <= high else 0
            if x > low:
                ans += dfs(root.left)
            if x < high:
                ans += dfs(root.right)
            return ans

        return dfs(root)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate optimize the traversal to reduce redundant checks?
question_mark
Does the candidate demonstrate understanding of tree pruning based on BST properties?
question_mark
Can the candidate implement both recursive and iterative solutions efficiently?

warning

常见陷阱

外企场景

error
Ignoring the BST properties and performing unnecessary traversal of both subtrees even when pruning is possible.
error
Misunderstanding the range inclusion, potentially excluding or including the bounds incorrectly.
error
Failing to handle deep recursion or stack overflow issues in large trees when using recursion.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider solving the problem using a breadth-first search (BFS) approach.
arrow_right_alt
What if the tree is not a BST? How would you adjust the approach?
arrow_right_alt
How does the solution change if the range is dynamically updated during traversal?

help

常见问题

外企场景

继续练习

#897 递增顺序搜索树 #1038 从二叉搜索树到更大和树 #783 二叉搜索树节点最小距离