Q938-二叉搜索树的范围和-简单-树

938. 二叉搜索树的范围和

Question

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

Example 1:

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

Example 2:

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

Note:

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

Apporach 1: 深度优先搜索

• 按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分以下四种情况讨论：

  • 节点为空

    返回 0。

  • 节点的值大于

    由于二叉搜索树右子树上所有节点的值均大于根节点的值，即均大于 ，故无需考虑右子树，返回左子树的范围和。

  • 节点的值小于

    由于二叉搜索树左子树上所有节点的值均小于根节点的值，即均小于 ，故无需考虑左子树，返回右子树的范围和。

  • 节点的值在 范围内

    此时应返回 节点的值、左子树的范围和、右子树的范围和这三者之和。

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

复杂度分析

• 时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。
• 空间复杂度：O(n)。空间复杂度主要取决于栈空间的开销。

Apporach 2: 广度优先搜索

使用广度优先搜索的方法，用一个队列 q 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        total = 0
        q = collections.deque([root])
        while q:
            node = q.popleft()
            if not node:
                continue
            if node.val > high:
                q.append(node.left)
            elif node.val < low:
                q.append(node.right)
            else:
                total += node.val
                q.append(node.left)
                q.append(node.right)

        return total

复杂度分析

• 时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。
• 空间复杂度：O(n)。空间复杂度主要取决于队列的空间。