【前言】

今天是刷题打卡第49天！

感谢老铁们的支持与陪伴，加油鸭。

原题：二叉搜索树的范围和（DFS+BFS） 

原题链接：力扣 

题目描述：

示例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
     
    
  
 

方法一：DFS

之前写过DFS解法，所以在这里就直接给出链接咯。

【手把手带你刷LeetCode】——11.二叉搜索树的范围和（DFS）_安然无虞的博客-CSDN博客【前言】https://blog.csdn.net/weixin_57544072/article/details/121202376

注意：二叉搜索树的特点就是左子树都比根要小，右子树都比根要大！ 

方法二：BFS

思路：

使用广度优先搜索的方法，用一个队列 q 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。

代码执行：

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * 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) {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              queue<TreeNode*>q;//定义一个队列
     
    
   

    

     

    
    

     
        //首先将根节点入队
     
    
   

    

     

    
    

     
        if(root)
     
    
   

    

     

    
    

     

                  q.push(root);
     
    
   

    

     

    
    

     
        int res = 0;
     
    
   

    

     

    
    

     
        while(!q.empty())//队列非空时循环继续
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            int n = q.size();//队列的长度
     
    
   

    

     

    
    

     
            for(int i = 0; i < n; i++)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     

                      TreeNode* t = q.front();//访问队首元素
     
    
   

    

     

    
    

     

                      q.pop();//队首元素出队
     
    
   

    

     

    
    

     
                //注意输入格式中有空节点，所以要加一个判断
     
    
   

    

     

    
    

     
                //当访问到的节点是空节点时，跳过该节点
     
    
   

    

     

    
    

     
                if(t == nullptr)
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     
                    continue;
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     
                //注意哦，由于是二叉搜索树，有它自己的特性
     
    
   

    

     

    
    

     
                //节点的值大于high时，只需要左子树入队
     
    
   

    

     

    
    

     
                if(t->val > high)
     
    
   

    

     

    
    

     

                          q.push(t->left);
     
    
   

    

     

    
    

     
                //节点的值小于low时，只需要右子树入队
     
    
   

    

     

    
    

     
                if(t->val < low)
     
    
   

    

     

    
    

     

                          q.push(t->right);
     
    
   

    

     

    
    

     
                //节点的值在low和high之间时，需要加上该节点值以及左右子树入队
     
    
   

    

     

    
    

     
                if(t->val >= low && t->val <= high)
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     

                          res += t->val;
     
    
   

    

     

    
    

     

                          q.push(t->left);
     
    
   

    

     

    
    

     

                          q.push(t->right);
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return res;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

结语

今天是刷题打卡第49天！

加油吧少年。

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

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