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

题目：

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