LeetCode 0938.二叉搜索树的范围和：深度优先搜索（可中序遍历）

【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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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 = right

class Solution:
    def dfs(self, root: Optional[TreeNode], l: int, r: int) -> None:
        if not root:
            return
        self.dfs(root.left, l, r)
        if l <= root.val <= r:
            self.ans += root.val
        self.dfs(root.right, l, r)

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        self.ans = 0
        self.dfs(root, low, high)
        return self.ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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