LeetCode如何实现二叉搜索树的范围和

发布时间：2021-12-15 10:29:52 作者：小新
来源：亿速云阅读：123

# LeetCode如何实现二叉搜索树的范围和

## 引言

二叉搜索树（Binary Search Tree, BST）是一种常见的数据结构，它具有高效的查找、插入和删除操作。在LeetCode等算法平台上，关于BST的问题频繁出现，其中"范围和"（Range Sum）问题是一个经典题目。本文将详细讲解如何实现二叉搜索树的范围和，包括问题描述、解题思路、代码实现以及复杂度分析。

## 问题描述

给定一个二叉搜索树的根节点 `root`，以及两个整数 `low` 和 `high`，返回树中所有位于 `[low, high]` 范围内的节点值的和。

**示例：**

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15 输出：32 解释：节点 7、10、15 的值位于 [7, 15] 范围内，它们的和为 32。


## 解题思路

### 二叉搜索树的特性

二叉搜索树具有以下特性：
- 左子树的所有节点值小于当前节点值。
- 右子树的所有节点值大于当前节点值。
- 左右子树也分别是二叉搜索树。

利用这些特性，我们可以高效地遍历BST并筛选出符合条件的节点。

### 方法一：递归中序遍历

中序遍历（左-根-右）BST会得到一个升序的节点值序列。我们可以在遍历过程中检查节点值是否在 `[low, high]` 范围内，并累加符合条件的值。

**步骤：**
1. 递归遍历左子树。
2. 检查当前节点值是否在范围内，如果是则累加。
3. 递归遍历右子树。

### 方法二：迭代中序遍历

使用栈模拟递归过程，避免递归的额外空间开销（递归调用栈）。

**步骤：**
1. 初始化栈和当前节点指针。
2. 循环直到栈为空且当前节点为null：
   - 将左子节点压栈，直到叶子节点。
   - 弹出栈顶节点，检查并累加符合条件的值。
   - 转向右子节点。

### 方法三：利用BST特性的剪枝

在递归或迭代过程中，如果当前节点值小于 `low`，则无需遍历左子树；如果当前节点值大于 `high`，则无需遍历右子树。这样可以减少不必要的遍历。

## 代码实现

### 递归中序遍历

```python
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: TreeNode, low: int, high: int) -> int:
        def inorder(node):
            if not node:
                return 0
            left_sum = inorder(node.left)
            current_val = node.val if low <= node.val <= high else 0
            right_sum = inorder(node.right)
            return left_sum + current_val + right_sum
        return inorder(root)

迭代中序遍历

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        stack = []
        current = root
        total = 0
        while stack or current:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            if low <= current.val <= high:
                total += current.val
            current = current.right
        return total

剪枝优化后的递归

class Solution:
    def rangeSumBST(self, root: 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.left, low, high) + self.rangeSumBST(root.right, low, high)

复杂度分析

时间复杂度

递归/迭代中序遍历：O(N)，其中N是树中节点数，每个节点被访问一次。
剪枝优化：最优情况下（如树完全不平衡），复杂度为O(log N)；最坏情况下（如树退化为链表），复杂度为O(N)。

空间复杂度

递归中序遍历：O(N)，递归调用栈的深度。
迭代中序遍历：O(N)，栈的空间。
剪枝优化：O(N)，递归调用栈的深度。

边界条件与测试用例

测试用例设计

常规BST：
- 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
- 输出：32
单节点树：
- 输入：root = [5], low = 1, high = 10
- 输出：5
范围外无节点：
- 输入：root = [10,5,15], low = 1, high = 4
- 输出：0
全范围覆盖：
- 输入：root = [10,5,15], low = 1, high = 20
- 输出：30

总结

通过本文的讲解，我们学习了三种解决BST范围和问题的方法： 1. 递归中序遍历：直观但空间复杂度较高。 2. 迭代中序遍历：避免了递归的开销。 3. 剪枝优化：利用BST特性减少遍历次数。

在实际应用中，剪枝优化通常是最高效的选择。理解BST的特性是解决此类问题的关键。

扩展思考

如果树不是BST，如何求解范围和？（提示：暴力遍历或前缀和）
如何修改算法以返回范围内的节点列表而非和？

”`

这篇文章总计约1400字，涵盖了问题分析、多种解法、代码实现和复杂度讨论，适合算法学习者和面试准备者阅读。