https://leetcode.com/problems/minimum-absolute-difference-in-bst
X. Inorder travsere
https://discuss.leetcode.com/topic/80796/java-o-n-time-inorder-traversal-solution
Indeed, hijacking a mutable array to emulate pass-by-reference reeks of a recovering C++ programmer (guilty as charged ;) )
中序遍历BST得到的序列是有序序列。因此创建一个vector存储中序遍历的每一个节点就得到一个有序序列,然后遍历这个有序序列,在遍历过程中求出两两之差并更新最小的绝对值之差就能得到结果。
http://www.liuchuo.net/archives/3714
X. [lower, upper bound]
https://discuss.leetcode.com/topic/80916/java-no-in-order-traverse-solution-just-pass-upper-bound-and-lower-bound
https://leetcode.com/problems/minimum-absolute-difference-in-bst/discuss/99905/Two-Solutions-in-order-traversal-and-a-more-general-way-using-TreeSet
Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.
X. Inorder travsere
https://discuss.leetcode.com/topic/80796/java-o-n-time-inorder-traversal-solution
Since this is a BST, the inorder traversal of its nodes results in a sorted list of values. Thus, the minimum absolute difference must occur in any adjacently traversed nodes. I use the global variable "prev" to keep track of each node's inorder predecessor.
int minDiff = Integer.MAX_VALUE;
TreeNode prev;
public int getMinimumDifference(TreeNode root) {
inorder(root);
return minDiff;
}
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
prev = root;
inorder(root.right);
}
class WrapInt{
int value;
}
public int getMinimumDifference(TreeNode root) {
List<Integer> prev = new ArrayList<>(); // contains at most 1 value
int[] min = new int[]{Integer.MAX_VALUE};
inorder(root, prev, min);
return min[0];
}
private void inorder(TreeNode root, List<Integer> prev, int[] min) {
if (root == null) return;
inorder(root.left, prev, min);
if (prev.isEmpty()) {
prev.add(root.val);
} else {
min[0] = Math.min(min[0], Math.abs(root.val - prev.get(0)));
prev.set(0, root.val);
}
inorder(root.right, prev, min);
}
https://discuss.leetcode.com/topic/80823/twof-solutions-in-order-traversal-and-a-more-general-way-using-treeset
Solution 1 - In-Order traverse, time complexity O(N), space complexity O(1).
Could you explain using Integer.MAX_VALUE;
int min = Integer.MAX_VALUE;
public class Solution {
int min = Integer.MAX_VALUE;//
Integer prev = null;
public int getMinimumDifference(TreeNode root) {
if (root == null) return min;
getMinimumDifference(root.left);
if (prev != null) {
min = Math.min(min, root.val - prev);
}
prev = root.val;
getMinimumDifference(root.right);
return min;
}
}
What if it is not a
BST
? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN)
time to lookup for the nearest values.
Solution 2 - Pre-Order traverse, time complexity O(NlgN), space complexity O(N).
TreeSet<Integer> set = new TreeSet<>();
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) return min;
if (!set.isEmpty()) {
if (set.floor(root.val) != null) {
min = Math.min(min, Math.abs(root.val - set.floor(root.val)));
}
if (set.ceiling(root.val) != null) {
min = Math.min(min, Math.abs(root.val - set.ceiling(root.val)));
}
}
set.add(root.val);
getMinimumDifference(root.left);
getMinimumDifference(root.right);
return min;
}
http://www.liuchuo.net/archives/3714
int getMinimumDifference(TreeNode* root) {
inOrder(root);
int result = INT_MAX;
for (int i = 1; i < tree.size(); i++)
result = min(result, tree[i] - tree[i-1]);
return result;
}
private:
vector<int> tree;
void inOrder(TreeNode* root) {
if (root->left != NULL) inOrder(root->left);
tree.push_back(root->val);
if (root->right != NULL) inOrder(root->right);
}
};
X. [lower, upper bound]
https://discuss.leetcode.com/topic/80916/java-no-in-order-traverse-solution-just-pass-upper-bound-and-lower-bound
def getMinimumDifference(self, root):
def mindiff(root, lo, hi):
if not root:
return float('inf')
return min(root.val - lo,
hi - root.val,
mindiff(root.left, lo, root.val),
mindiff(root.right, root.val, hi))
return mindiff(root, float('-inf'), float('inf'))
X.https://leetcode.com/problems/minimum-absolute-difference-in-bst/discuss/99905/Two-Solutions-in-order-traversal-and-a-more-general-way-using-TreeSet
What if it is not a
BST
? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN)
time to lookup for the nearest values.
Solution 2 - Pre-Order traverse, time complexity O(NlgN), space complexity O(N).
public class Solution {
TreeSet<Integer> set = new TreeSet<>();
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) return min;
if (!set.isEmpty()) {
if (set.floor(root.val) != null) {
min = Math.min(min, root.val - set.floor(root.val));
}
if (set.ceiling(root.val) != null) {
min = Math.min(min, set.ceiling(root.val) - root.val);
}
}
set.add(root.val);
getMinimumDifference(root.left);
getMinimumDifference(root.right);
return min;
}
}