【前言】
今天是力扣打卡第11天！
感谢铁汁们的陪伴，一起加油鸭！！
在第9天的时候写过这道题的递归解题方法，其实DFS使用的解题思想就是递归，所以大同小异啦。大家简单看一下纯递归的解法：
https://blog.csdn.net/weixin_57544072/article/details/121196600?spm=1001.2014.3001.5502
原题：二叉搜索树的范围和（DFS解法）
题目描述：
给定二叉搜索树的根结点 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
题解 ：
全都在代码里头咯。
代码执行：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int rangeSumBST(struct TreeNode* root, int low, int high){ // //方法一：递归法 // //找边界 // if(root == NULL){ // return 0; // } // //左子树 // int leftSum = rangeSumBST(root->left, low, high); // //右子树 // int rightSum = rangeSumBST(root->right, low, high); // int result = leftSum + rightSum; // //判断根节点 // if(root->val >= low && root->val <= high){ // result += root->val; // } // return result; //方法二：DFS //判断特殊情况 if(root == NULL){ return 0; } //如果根节点的值大于high，那么右子树不满足，此时只需要判断左子树 if(root->val > high){ return rangeSumBST(root->left, low, high); } //如果根节点的值小于low，那么左子树一定不满足，此时只需要判断右子树 if(root->val < low){ return rangeSumBST(root->right, low, high); } //否则如果根节点的值在low和high之间，那么三者都需要判断 return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high); }
复杂度分析：
时间复杂度：O(N), 取决于二叉搜索树的节点数；
空间复杂度：O(N)，取决于递归调用栈空间的开销。
总结：
今天是力扣打卡第11天！
时间很紧，博主和铁汁们一起坚持，加油！！
