【LetMeFly】938.二叉搜索树的范围和：深度优先搜索（可中序遍历）

力扣题目链接：https://leetcode.cn/problems/range-sum-of-bst/

给定二叉搜索树的根结点 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 * 104] 内
• 1 <= Node.val <= 105
• 1 <= low <= high <= 105
• 所有 Node.val 互不相同

方法一：深度优先搜索（可中序遍历）

二叉搜索树有一个性质：其中序遍历得到的序列递增。

但其实我们不使用这个性质也可以，只需要将其当作一个普通的二叉树。

遍历二叉树（可以中序也可以其他）并且在遍历途中判断当前节点的值是否在[low, high]之间。如果是则累加之。

• 时间复杂度$O(N)$，其中$N$是二叉树节点的个数
• 空间复杂度$O(N)$

AC代码

C++

class Solution {  // AC,96.46%,73.98%
private:int ans;void dfs(TreeNode* root, int l, int r) {if (!root) {return;}dfs(root->left, l, r);if (root->val >= l && root->val <= r) {ans += root->val;}dfs(root->right, l, r);}
public:int rangeSumBST(TreeNode* root, int low, int high) {ans = 0;dfs(root, low, high);return ans;}
};

Python

# from typing import Optional# # 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 = rightclass Solution:def dfs(self, root: Optional[TreeNode], l: int, r: int) -> None:if not root:returnself.dfs(root.left, l, r)if l <= root.val <= r:self.ans += root.valself.dfs(root.right, l, r)def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:self.ans = 0self.dfs(root, low, high)return self.ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136306565