力扣——二叉搜索树的范围和

题目：

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
提示：
树中的结点数量最多为 10000 个。
最终的答案保证小于 2^31。

思路：

首先是题意：这道题的意思就是，找出在给定左右节点范围中的节点数的和。

所以我们可以遍历所有节点，于是我们可以使用递归。

法一，使用递归但是方法作用与法二不同，作用写在了代码的第一句，法三就是用while循环，遍历每个节点

代码：

main函数：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}


//递归实现深度优先搜索
public class 二叉搜索树的范围和 {
    static int result;
    static int ans;
    public static void main(String[] args) {
        result = 0;
        //第一层
        TreeNode node = new TreeNode(10);
        //第二层
        node.left = new TreeNode(5);
        node.right = new TreeNode(15);
        //第三层
        node.left.left = new TreeNode(3);
        node.left.right = new TreeNode(7);
        node.right.right = new TreeNode(18);
        //法一，递归但是方法作用与法二不同，递归实现深度优先遍历：
//        dfs(node,7, 15);
//        System.out.println(result);
        //法二：
//        System.out.println(dfs2(node,7,15));
        //法三,迭代实现深度优先遍历:
        f3(node,7,15);
        System.out.println(ans);

    }

法一：

//当前节点是否能进入result的和,遍历了所有节点
    public static void dfs(TreeNode node, int l, int r) {
        if (node != null){
            if (l <= node.val && node.val <= r) {
                result += node.val;
            }
            //这里必须要遍历每个节点，所以需要node.val > l ,dfs(node.left,l,r)
            if (node.val > l) dfs(node.left,l,r);
            if (node.val < r) dfs(node.right,l,r);
        }
    }

法二：

//该树的满足范围的和,，没有遍历所有节点
    //如果当前节点的值小于left，和等于右子数之和
    //如果当前节点的值大于right，和等于左子数之和
    //如果当前节点的值在范围里，和等于右子数+左子树之和+当前节点的值
    private static int dfs2(TreeNode node, int l, int r) {
        if (node == null) {
            return 0;
        }
        if (node.val < l){
            return dfs2(node.right,l,r);
        }
        if (node.val > r){
            return dfs2(node.left,l,r);
        }
        return dfs2(node.left,l,r)+dfs2(node.right,l,r)+node.val;
    }

法三：

//迭代实现深度优先遍历，遍历了所有节点
    public static int f3(TreeNode root,int L, int R){
        ans = 0;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }