由于在中序遍歷下的BST得到的值依然是依次有序的，利用這一點烹植，保存前一個點和現(xiàn)有點進行比較就好了，時間是O（N）愕贡。
證明如下：對于一個BST草雕，左側(cè)是比他小的數(shù)，右側(cè)是比他大的數(shù)固以，采取中序遍歷時墩虹，當我們遍歷左半部分時嘱巾，可以遞歸的發(fā)現(xiàn)，最左邊的結(jié)點是最先訪問的诫钓，最右邊的結(jié)點是最后訪問的旬昭。當我們回到root時，前一個訪問的結(jié)點是左半部分的最右結(jié)點菌湃，如果攤平數(shù)組稳懒，可以得到這兩個數(shù)肯定是相鄰的，于是問題就變成了順序遍歷有序數(shù)組得到最小差慢味。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode pre = null;
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
getDifference(root);
return min;
}
private void getDifference(TreeNode root)
{
if(root==null)return ;
getDifference(root.left);
if(pre!=null)
{
min=Math.min(min,Math.abs(pre.val-root.val));
}
pre=root;
getDifference(root.right);
}
}
