LeetCode 938.二叉搜索树的范围和（递归，BFS）

快来打我* 2024-05-08 06:15 135阅读 0赞

## 题目 ##

[题目链接][Link 1]

## 思路 ##

**递归**：根据二叉搜索树的性质（左子树的值都小于根节点，右子树的值都大于根节点）进行分类，如果当前根节点值为空，直接返回零；如果当前根节点值大于right，需要返回左子树的范围和；如果当前根节点值小于left，需要返回右子树的范围和；如果当前根节点值在\[left, right\] 之间，则返回左子树的范围和和右子树的范围和以及当前根节点的值  
**BFS**：将符合条件的节点放入队列中，但只有范围之内的值才会加入sum

## 代码 ##

递归版

class Solution {
        
        public int rangeSumBST(TreeNode root, int low, int high) {
        
            if(root == null) return 0;
            else if(root.val > high) return rangeSumBST(root.left, low, high);
            else if(root.val < low) return rangeSumBST(root.right, low, high);
            return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + root.val;
        }
    }

BFS版

class Solution {
        
        public int rangeSumBST(TreeNode root, int low, int high) {
        
            int sum = 0;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(root);
            while(!q.isEmpty()) {
        
                TreeNode node = q.poll();
                if(node == null) continue;
                else if(node.val > high) q.offer(node.left);
                else if(node.val < low) q.offer(node.right);
                else {
        
                    sum += node.val;
                    q.offer(node.left);
                    q.offer(node.right);
                }
            }
            return sum;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/range-sum-of-bst/