Leetcode530. 二叉搜索树的最小绝对差

题目

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

示例 :

输入:

   1
    \
     3
    /
   2

输出:
1

解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
注意: 树中至少有2个节点。

C++代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    int lastValue = -1;
    int delta = INT32_MAX;
    int getMinimumDifference(TreeNode* root) {
        if (root) travel(root);
        return delta;
     }
    
    void travel(TreeNode * root) {
        if (root->left) travel(root->left);
        if (lastValue != -1 && root->val - lastValue < delta) {
            delta = root->val - lastValue;
        }
        lastValue = root->val;
        if (root->right) travel(root->right);
    }
};
int main(int argc, const char * argv[]) {
    // insert code here...
    Solution solution;
    TreeNode * node = new TreeNode(1);
    node->right = new TreeNode(3);
    node->right->left = new TreeNode(2);
    cout << solution.getMinimumDifference(node) << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst