题目描述

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

样例

输入：

   1
    \
     3
    /
   2

输出：
1

解释：
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

注意

• 树中至少有 2 个节点。

算法

(中序遍历) $O(n)$

1. 对二叉搜索树进行中序遍历，得到的是单调递增的序列，故可以在中序遍历的过程中，记录上一次遍历到的值，然后和本次遍历的值求差得到一组差值。
2. 所有的差值取最小值就是答案。

时间复杂度

• 中序遍历每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储递归的系统栈。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int ans, last;
    bool first;

    void traverse(TreeNode *rt) {
        if (!rt) return;
        traverse(rt->left);

        if (!first) ans = min(ans, rt->val - last);
        first = false;
        last = rt->val;

        traverse(rt->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        ans = INT_MAX;
        first = true;
        traverse(root);
        return ans;
    }
};