题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

)

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

解答

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = INT_MAX; // 最小差值
    vector<int> ivec;
    TreeNode *pre = nullptr;
    void traversal(TreeNode *cur)
    {
        if(cur == nullptr) return ;
        traversal(cur->left);
        if(pre != nullptr)
        {
          	// 中序遍历过程中每次用当前节点减去前一个节点
            res = min(res, cur->val - pre->val);
        }
        pre = cur;
        traversal(cur->right);
    }
    int getMinimumDifference(TreeNode* root) {
        // 中序遍历中计算，记录前一个节点
        traversal(root);
        return res;
    }

    // 中序遍历存到数组
    int getMinimumDifference1(TreeNode* root) {
        // 中序遍历得到升序序列
        inorder(root);
        return res;
    }

    void inorder(TreeNode* root)
    {
        if(root == nullptr) return;

        inorder(root->left);
        //
        ivec.push_back(root->val);
        if(ivec.size() >= 2 && abs(root->val - ivec[ivec.size() - 2]) < res) res = abs(root->val - ivec[ivec.size() - 2]);
        inorder(root->right);
    }
};