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

一、概述

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

测试用例：

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

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

思路

        思路1：其实通过不同的遍历方式获取数中所有结点的值并存储到数组之中，之后在遍历数组中的所有元素，比较元素值的情况，进行累加。但其实完全可以遍历过程中就进行统计，因为是二叉搜素树，为有序的，所以完全可以遍历过程中进行比较。

        思路2：楼主使用较多的为dfs(深度优先遍)，所以这里使用dfs方式进行搜索并计算范围和，有以下几种情况：

root为空指针，则直接返回0；root结点的val值大于high，则其右子树的所有结点的值肯定大于high的，所以直接探索左子树的范围和；root结点的val值小于low，则其左子树的所有结点的值肯定小于high的，所以直接探索右子树的范围和root的val值处于[low,high]之间，则累加即可，同时需要往root的左右两个子节点处进行遍历，返回这三者之和。

复杂度：

时间复杂度：因为要遍历完所有结点，所以为O(n)，其中 n 是二叉搜索树的节点数。 空间复杂度：其实和思路1的方式相同，O(n)

代码

#include

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(nullptr), right(nullptr) {}

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution{

public:

int rangeSumBST(TreeNode *root, int low, int high){

if(root == nullptr){

return 0;

}

if (root->val > high)

{

return rangeSumBST(root->left, low, high);

}

if (root->val < low)

{

return rangeSumBST(root->right, low, high);

}

return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);

}

};

int main(){

TreeNode* root = new TreeNode(10);

root->left = new TreeNode(5);

root->right = new TreeNode(15);

root->left->left = new TreeNode(3);

root->left->right = new TreeNode(7);

root->right->right = new TreeNode(18);

int low = 7;

int high = 15;

int res = Solution().rangeSumBST(root, low, high);

cout << "res: " << res << endl;

// 释放内存

delete root;

return 0;

}

        

精彩内容

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：