这题是让找一个BST中两个node的Absolute difference，val之差的最小绝对值。
想到BST你一定要先想到inorder traverse是递增的。我看到这题第一个想法竟然是找每一个节点的左子树的最右结点，以及右子树的最左结点，这想法看似没错，但我不知道怎么写。
然后我想到inorder traverse的时候，发现自己竟然不能迅速写出中序遍历二叉树的代码。。想了半天才写出来。
遍历二叉树是这样的：
1 递归左子树
2 做想做的事，比如visit node
3 递归右子树
其中第二部不用递归了啊，只要做事就行了。
AC的代码
一开始我把min和前一个结点的值都用做了全局成员变量，这样可以避免在参数中传递带来的思考复杂。
int min = Integer.MAX_VALUE;
int preVal = -1;
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return min;
}
private void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
if (preVal != -1) {
min = Math.min(root.val - preVal, min);
}
preVal = root.val;
inOrder(root.right);
}
AC之后我尝试把全局变量搞成参数。
首先，
下面的代码是不行的
//错误的示范
public int getMinimumDifference(TreeNode root) {
return inOrder(root, -1, Integer.MAX_VALUE);
}
private int inOrder(TreeNode root, int pre, int min) {
if (root == null) return 0;
inOrder(root.left, pre, min);
if (pre != -1) {
min = Math.min(root.val - pre, min);
}
pre = root.val;
inOrder(root.right, pre, min);
return min;
}
为什么，因为最后返回的min是第一次传进去的min也就是 Integer.MAX_VALUE。记住，递归永远是从什么地方进去就从什么地方出来，所以传一个int类型的基本数据类型，它的内存地址每次递归都会随着int值的变化而变化的，那等你回到最初的起点的时候，return的min就仍然是第一次传入的min。
于是我把min改成了数组：
//错误的示范
public int getMinimumDifference(TreeNode root) {
int[] min = new int[1];
min[0] = Integer.MAX_VALUE;
return inOrder(root, -1, min);
}
private int inOrder(TreeNode root, int pre, int[] min) {
if (root == null) return 0;
inOrder(root.left, pre, min);
if (pre != -1) {
min[0] = Math.min(root.val - pre, min[0]);
}
pre = root.val;
inOrder(root.right, pre, min);
return min[0];
}
但这么做仍然不行，比如5,4,7会返回2而不是1. 为什么？还是参数的问题。当我遍历完了4回到5的时候，这时候pre又是-1了，而不是之前的4. 当然可以把pre也弄成数组，不过这就跟全局变量一样了。
那总结一个规律：
凡是想要维护一个值的，比如前一个状态的值，不要用参数传递，用全局变量吧。
我看了下，solutions的代码基本都跟我的一模一样，用了两个全局变量。
另外，有个人提出了如果不是BST的follow up：
用TreeSet来实现，floor和ceil函数分别可以找比给定函数小的和大的那个最近的那个数。查找时间是O(NlogN)。我也想了这个问题，不过我是想遍历一遍放到arraylist里然后排序，这样总时间就是O(N2)了。
他下面用了preorder，其实我想了一下，中序和后序似乎也是可以的，反正每个结点都要跟其他结点对比一次。
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;
}
}
