LeetCode 938. 二叉搜索树的范围和

938. 二叉搜索树的范围和

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-bst/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 创建二叉搜索树

static class TreeNode implements Comparable<TreeNode> {
        private Integer val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int[] arr) {
            if (arr == null || arr.length == 0) throw new NullPointerException("array is empty");
            this.val = arr[0];
            TreeNode root = this;
            for (int i = 1; i < arr.length; i++) {
                add(root, arr[i]);
            }
        }


        public TreeNode add(TreeNode root, Integer val) {
            if (root == null) return new TreeNode(val);
            if (val.compareTo(root.val) < 0) root.left = add(root.left, val);
            if (val.compareTo(root.val) > 0) root.right = add(root.right, val);
            return root;
        }

         @Override
        public int compareTo(TreeNode o) {
            return this.val.compareTo(o.val);
        }

• 1.递归法

思路 : 从宏观上考虑

1. 当最小边界 L 都比根节点大时，我们所需的元素一定在root的右子树
2. 当最大边界都比 根节点小时， 我们所需的元素一定在root的左子树
3. 其他情况既需要查询左子树，又需要查询右子树，还要加上根节点的值

public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        if (root.val < L) return rangeSumBST(root.right, L, R);
        if (root.val > R) return rangeSumBST(root.left, L, R);
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }

复杂度分析：

• 时间复杂度：O(h), h为二叉搜索树的深度

• 空间复杂度：O(n), n为元素数量，由于使用递归，空间复杂度可能达到O(n)

• 2. 中序遍历

思路：

1. 先遍历二叉搜索树的左子树
2. 接下来遍历二叉搜索树的根节点
3. 最后在遍历二叉搜索树的右子树

 static int num = 0;
    public static int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        inOrder(root, L, R);
        return num;
    }

    public static void inOrder(TreeNode root, int L, int R) {
        if (root == null) return;
        inOrder(root.left, L, R);
        if (root.val >= L && root.val <= R) {
            num += root.val;
        }
        inOrder(root.right, L, R);
    }

复杂度分析：

• 时间复杂度：O(h), h为二叉搜索树的深度

• 空间复杂度：O(n), n为元素数量，由于使用递归，空间复杂度可能达到O(n)

• 3. 前序遍历

思路：

1. 先遍历二叉搜索树的根节点
2. 接下来遍历二叉搜索树的左子树
3. 最后在遍历二叉搜索树的右子树

static int num = 0;
 public static int rangeSumBST3(TreeNode root, int L, int R) {
        if (root == null) return 0;
        preOrder(root, L, R);
        return num;
    }

    private static void preOrder(TreeNode root, int L, int R) {
        if (root == null) return;
        if (root.val >= L && root.val <= R) {
            num += root.val;
        }
        preOrder(root.left, L, R);
        preOrder(root.right, L, R);
    }

复杂度分析：

• 时间复杂度：O(h), h为二叉搜索树的深度

• 空间复杂度：O(n), n为元素数量，由于使用递归，空间复杂度可能达到O(n)

• 4. 前序遍历的非递归实现

思路：使用栈的后进先出(LIFO)特性

1. 现将二叉搜索树的根节点压入栈中
2. 出栈栈顶元素，在依次将右子树、左子树压入栈中

public static int rangeSumBST(TreeNode root, int L, int R) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.val >= L && cur.val <= R) {
                sum += cur.val;
            }
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
        return sum;
    }

复杂度分析：

• 时间复杂度：O(h), h为二叉搜索树的深度

• 空间复杂度：O(n), n为元素数量，由于使用了栈，空间复杂度会达到O(n)

• 5. 后序遍历

思路：

1. 先遍历二叉搜索树的左子树
2. 接下来遍历二叉搜索树的右子树
3. 最后在遍历二叉搜索树的根节点

static int num = 0;
public static int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        postOrder(root, L, R);
        return num;
    }

    private static void postOrder(TreeNode root, int L, int R) {
        if (root == null) return;
        postOrder(root.left, L, R);
        postOrder(root.right, L, R);
        if (root.val >= L && root.val <= R) {
            num += root.val;
        }
     }

复杂度分析：

• 时间复杂度：O(h), h为二叉搜索树的深度

• 空间复杂度：O(n), n为元素数量，由于使用了递归，空间复杂度会达到O(n)

• 测试用例

 public static void main(String[] args) {
         int[] arr = new int[] {10, 5, 15, 3, 7, 0, 18};
         TreeNode treeNode = new TreeNode(arr);
         System.out.println(rangeSumBST4(treeNode, 7, 15));
    }

• 结果

5

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github