938.二叉搜索树的范围和

题目描述（简单难度）

给定二叉搜索树的根结点 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

解法一 递归法

思路:

遍历所有节点，不限遍历的方式。这种不限于二叉搜索树。
这种方法，其实找了很多不该找的节点，比较了很多不用比较的节点，浪费了一定的时间。利用二叉搜索树这一特性。

    public int rangeSumBST(TreeNode root, int low, int high) {
        //判断，结点为null，则不存在左右两个孩子，值就返回0
        if (root==null){
            return 0;
        }
        //求左边的和
        int leftSum = rangeSumBST(root.left ,low, high);
        //求右边的和
        int rightSum = rangeSumBST(root.right,low,high);
        //左边sum+右边sum就是整颗树的和
        int result = leftSum + rightSum;
        //判断结点值是否符合题意
        if (root.val >= low && root.val <= high){
            //符合题意的值加到结果上
            result = result + root.val;
        }
        return result;
    }

解法二 BFS(宽度优先遍历)

思路:

一层一层的遍历，两个while循环，外面大while循环是遍历每一层，里面小while循环是遍历每一层的每一个结点

public int rangeSumBST2(TreeNode root, int low, int high) {
        if (root==null){
            return 0;
        }
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //这里的queue的值是在第二个while循环中添加的。
        while (queue.size()>0){
            //size指针控制小while循环的遍历
            int size = queue.size();
            //循环遍历这一‘层’的结点
            //寻找符合题意的值，并将每个结点的左右子树加到queue
            while (size>0){
                TreeNode cur = queue.poll();
                //判断当前结点的值是否符合要求
                if (cur.val>=low && cur.val <= high){
                    result = result + cur.val;
                }
                //把当前结点的左子树加如到queue
                if (cur.left != null){
                    queue.add(cur.left);
                }
                //把当前结点的右子树加如到queue
                if (cur.right != null){
                    queue.add(cur.right);
                }
                size--;
            }
        }
        return 0;
    }