-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-530-Minimum-Absolute-Difference-in-BST.java
62 lines (56 loc) · 1.97 KB
/
LeetCode-530-Minimum-Absolute-Difference-in-BST.java
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 1.Do an inorder traversal using a Stack.
// public int getMinimumDifference(TreeNode root) {
// Stack<TreeNode> stack = new Stack<>();
// TreeNode curr = root;
// TreeNode prev = null;
// int minAbsDiff = Integer.MAX_VALUE;
// while (curr != null || !stack.isEmpty()) {
// if (curr != null) {
// stack.push(curr);
// curr = curr.left;
// } else {
// // we reached the left most node
// // start processing current nodes in the tree
// curr = stack.pop();
// if (prev != null) {
// if (Math.abs(prev.val - curr.val) < minAbsDiff) {
// minAbsDiff = Math.abs(prev.val - curr.val);
// }
// }
// prev = curr;
// curr = curr.right; // proceed the right tree of curr node
// }
// }
// return minAbsDiff;
// }
//2.DFS to do inorder traversal
TreeNode prev = null;
public int getMinimumDifference(TreeNode root) {
int[] minAbsDiff = new int[] {Integer.MAX_VALUE};
dfs(root, minAbsDiff);
return minAbsDiff[0];
}
private void dfs(TreeNode root, int[] minAbsDiff) {
// root should not be null
if (root.left != null) dfs(root.left, minAbsDiff);
// process the current root
if (prev != null) {
// current root is not the first node in the inorder traversal
if (Math.abs(prev.val - root.val) < minAbsDiff[0]) {
minAbsDiff[0] = Math.abs(prev.val - root.val);
}
}
prev = root;
if (root.right != null) dfs(root.right, minAbsDiff);
}
}