关于算法:力扣二叉搜索树的范围和

题目：

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