-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathLeetCode_938_2.java
More file actions
104 lines (95 loc) · 2.7 KB
/
LeetCode_938_2.java
File metadata and controls
104 lines (95 loc) · 2.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
//
// The binary search tree is guaranteed to have unique values.
//
//
//
//
// Example 1:
//
//
//Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
//Output: 32
//
//
//
// Example 2:
//
//
//Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
//Output: 23
//
//
//
//
// Note:
//
//
// The number of nodes in the tree is at most 10000.
// The final answer is guaranteed to be less than 2^31.
//
//
//
package com.llz.algorithm.algorithm2019.secondweek;
import com.llz.algorithm.algorithm2019.firstweek.TreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class LeetCode_938_2 {
private int sum = 0;
public int rangeSumBSTByTraverse(TreeNode root, int L, int R) {
dfs(root, L, R);
return sum;
}
/**
* There is time cost difference depends on how you deal with the case of null root.
* If you write "if (root == null) return;",then the function will backtrack
* and cost more time than if you just eliminate the "root equals null" situation by writing
* "if (root != null) {...} ".
* Time complexity is O(n) and space complexity is O(h)(h is height of BST).
* If the given BST is balanced, then the time complexity is O(logn) and space complexity is O(logn) as well.
*
* @param root
* @param L
* @param R
*/
public void dfs(TreeNode root, int L, int R) {
if (root != null) {
if (root.val >= L && root.val <= R)
sum += root.val;
if (root.val > L) dfs(root.left, L, R);
if (root.val < R) dfs(root.right, L, R);
}
}
/**
* Use stack to record the possible target nodes.
* Time complexity is O(n) and space complexity is O(h)(h is height of BST).
* If the given BST is balanced, then the time complexity is O(logn) and space complexity is O(logn) as well.
* @param root
* @param L
* @param R
* @return
*/
public int rangeSumBSTByIteration(TreeNode root, int L, int R) {
if (root == null) return 0;
int sum = 0;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
if (root.val >= L && root.val <= R)
sum += root.val;
if (root.val > L && null != root.left) stack.push(root.left);
if (root.val < R && null != root.right) stack.push(root.right);
}
return sum;
}
}