Programming Skills: Minimum Distance Between BST Nodes

[題目]
https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

Given a Binary Search Tree (BST) with the root node, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

The size of the BST will be between 2 and 100.
The BST is always valid, each node's value is an integer, and each node's value is different.

給一個BST Tree的root node (注意喔原題中input用array表示只是為了說明題目時書寫上的方便，所以用array表示tree，但實際function的input是tree node)。
任兩點的value相減會有一個差值，求最小的差值為何?
請注意差值必為positive number，也就是你相減的時候要取絕對值。

[思路]

先思考"最小的差值"這件事 : 若題目簡化成"給你一堆數字，求最小差值"你該怎麼做?
答案很簡單，任選兩個值，求差值，所有可能的選擇中最小的就是答案。
N個數字選兩個的方法有N*N-1種，因此是O(N^2)。

那有沒有好點的做法 ? 有 !
如果這堆數字已經排序好了，那麼最小的差值只會出現在相鄰的兩數字中。
e.g. 4 6 7 9中最小的差值必定是4~6 or 6~7 or 7~9，你如果硬是要跳過中間人，只會使差值更大。所以如果排序好了的話，就順序走過array，簡查相鄰的人即可。花費為O(N)，讚!

但題目給我的是BST root node，又不是一串數字，該怎麼辦?
這邊是考你知不知道BST的特性之一，也就是你去inorder traverse BST的話，得出的數列是排序好的數列。所以你只要inorder traverse一遍就得到sorted array了。

總結一下
1.若數字已經排序好了，只要花O(N)走一遍這個sorted array，計算哪兩個相鄰的人的差最小。
2.Inorder traverse BST tree就可以得到sorted array

綜合1,2兩點就可以解這題了


class Solution {
public:
    
    vector<int> sorted;
    void inorder(TreeNode* root){
        if(root==NULL) return;
        inorder(root->left);
        sorted.push_back(root->val);
        inorder(root->right);
    }
    
    int minDiffInBST(TreeNode* root) {
        inorder(root);
        int mindiff=INT_MAX;
        for(int i=0;i<sorted.size()-1;i++)
            mindiff = min(mindiff, abs(sorted[i] - sorted[i+1]));        
        return mindiff;
    }
};