leetcode 链接：530. 二叉搜索树的最小绝对差

题目

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

  1. 输入：
  3.    1
  4.     \
  5.      3
  6.     /
  7.    2
  9. 输出：
  10. 1
  12. 解释：
  13. 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

解答 & 代码

利用二叉搜索树的性质：中序遍历得到的的是递增序列，因此在中序遍历的过程中，用当前节点和前一个节点的差值来更新 minDiff 即可

/**
 * 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 {
private:
    // 中序遍历搜索二叉树，pre 为前一个节点的值（注意加引用符&），minDiff是最小绝对差
    void inOrder(TreeNode* root, int& pre, int& minDiff)
    {
        // 递归结束条件
        if(root == nullptr)
            return;

        // 先遍历左子树
        inOrder(root->left, pre, minDiff);

        // 再处理当前根节点
        if(pre >= 0 && root->val - pre < minDiff)
            minDiff = root->val - pre;
        pre = root->val;

        // 最后遍历右子树
        inOrder(root->right, pre, minDiff);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        int minDiff = INT_MAX;
        int pre = -1;
        inOrder(root, pre, minDiff);
        return minDiff;
    }
};

执行结果：

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 83.53% 的用户
内存消耗：24.5 MB, 在所有 C++ 提交中击败了 89.27% 的用户