【前言】

今天是力扣打卡第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天！

时间很紧，博主和铁汁们一起坚持，加油！！ 

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121202376