LeetCode 938. 二叉搜索树的范围和
2019-07-16 本文已影响0人
TheKey_
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.递归法
思路 : 从宏观上考虑
- 当最小边界 L 都比根节点大时，我们所需的元素一定在root的右子树
- 当最大边界都比 根节点小时， 我们所需的元素一定在root的左子树
- 其他情况既需要查询左子树，又需要查询右子树，还要加上根节点的值
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. 中序遍历
思路：
- 先遍历二叉搜索树的左子树
- 接下来遍历二叉搜索树的根节点
- 最后在遍历二叉搜索树的右子树
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. 前序遍历
思路：
- 先遍历二叉搜索树的根节点
- 接下来遍历二叉搜索树的左子树
- 最后在遍历二叉搜索树的右子树
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)特性
- 现将二叉搜索树的根节点压入栈中
- 出栈栈顶元素，在依次将右子树、左子树压入栈中
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. 后序遍历
思路：
- 先遍历二叉搜索树的左子树
- 接下来遍历二叉搜索树的右子树
- 最后在遍历二叉搜索树的根节点
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
