783. Minimum Distance Between BST Node
给一棵二元搜寻树，
求任意两节点差值的最小值。
Example 1:
Input: root = [4, 2, 6, 1, 3]
Output: 1
Explanation:
https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg
[2, 1], [2, 3], [4, 3] 差值都是 1
Example 2:
Input: root = [1, 0, 48, null, null, 12, 49]
Output: 1
Explanation:
https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg
[1, 0], [48, 49] 差值皆为 1
解题思路:
给定的是一颗二元搜寻树，
最接近当前节点的值会是左子树的最大值以及右子树的最小值，
找到后进行计算看看哪个比较小，
对所有子树都做过一次就能找到答案，
但要避免重复走访会增加时间复杂度。
C++ code:
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX;
recursive(root, ans);
return ans;
}
pair<int, int> recursive(TreeNode* root, int &ans){
if(!root) return {0, 0};
auto [lmin, lmax] = recursive(root->left, ans);
auto [rmin, rmax] = recursive(root->right, ans);
if(root->left) ans = min(ans, abs(root->val - lmax));
if(root->right) ans = min(ans, abs(root->val - rmin));
return {root->left ? lmin : root->val, root->right ? rmax :
root->val};
}
};