(Leetcode 2021 刷题计划) 783. 二叉搜索树节点最小距离

示例 1：
输入：root = [4,2,6,1,3]
输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode *cur = root, *prev = root;
        int res = INT_MAX;
        while (cur != nullptr || !stk.empty()) {
            while (cur != nullptr) {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            // 用来排除根节点无左节点从而产生最小值为 0 的情况
            if (cur != prev) res = min(res, abs(cur->val - prev->val));
            prev = cur;
            cur = cur->right;
        }
        return res;
    }
};

class Solution {
public:
    void dfs(TreeNode* root, int& pre, int& ans) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left, pre, ans);
        if (pre == -1) {
            pre = root->val;
        } else {
            ans = min(ans, root->val - pre);
            pre = root->val;
        }
        dfs(root->right, pre, ans);
    }
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX, pre = -1;
        dfs(root, pre, ans);
        return ans;
    }
};