Day112 | 灵神 | 二叉树 | 二叉搜索树的范围和

938.二叉搜索树的范围和

938. 二叉搜索树的范围和 - 力扣（LeetCode）

思路：

最直接的思路当然是直接前序遍历一遍，碰到在一个区间的就加到和里面

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int res=0;
    void dfs(TreeNode* t, int low, int high)
    {
        if(t==nullptr)
            return ;
        if(t->val<=high&&t->val>=low)
            res+=t->val;
        dfs(t->left,low,high);
        dfs(t->right,low,high);
    }
    int rangeSumBST(TreeNode* root, int low, int high) {
        dfs(root, low, high);
        return res;
    }
};

加上二叉搜索树的性质就是用后序遍历来写，递归函数返回值就返回当子树的范围和

1.当前结点值大于high的值说明右子树的所有值在范围外，只搜索左子树

2.当前结点值小于low的值说明左子树的所有值在范围外，只搜索右子树

3.在范围内那么左右子树都得继续搜索，返回三者的和

cpp
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if(root==nullptr)
            return 0;
        if(root->val<low)
            return rangeSumBST(root->right,low,high);
        if(root->val>high)
            return rangeSumBST(root->left,low,high);
        return root->val+rangeSumBST(root->left,low,high)+rangeSumBST(root->right,low,high);
    }
};