Description

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:Input:   1    \     3    /   2Output:1Explanation:The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).Note: There are at least two nodes in this BST.

Discuss

C++ 7 lines, O(n) run-time O(h) memory

In-order traversal of BST yields sorted sequence. So, we just need to subtract the previous element from the current one, and keep track of the minimum. We need O(1) memory as we only store the previous element, but we still need O(h) for the stack.

• 参数在inorder()里面传递

void inorderTraverse(TreeNode* root, int& val, int& min_dif) {    if (root->left != NULL) inorderTraverse(root->left, val, min_dif);    if (val >= 0) min_dif = min(min_dif, root->val - val);    val = root->val;    if (root->right != NULL) inorderTraverse(root->right, val, min_dif);}int getMinimumDifference(TreeNode* root) {    auto min_dif = INT_MAX, val = -1;    inorderTraverse(root, val, min_dif);    return min_dif;}// 下面code为我据此重写的inorder, 细节略有区别class Solution {private:    void inorder(TreeNode *root, int &pre, int &minval) {        if (!root) return;        inorder(root->left, pre, minval);        /* 以下为visit 部分 */        if (pre >= 0) minval = min(minval, root->val - pre);        pre = root->val;        /* 以上 */        inorder(root->right, pre, minval);    }public:    int getMinimumDifference(TreeNode *root) {        int pre = -1, minval = 99999;        inorder(root, pre, minval);        return minval;    }};

• 参数在外 | member variables

class Solution {    int min_dif = INT_MAX, val = -1;public:int getMinimumDifference(TreeNode* root) {    if (root->left != NULL) getMinimumDifference(root->left);    if (val >= 0) min_dif = min(min_dif, root->val - val);    val = root->val;    if (root->right != NULL) getMinimumDifference(root->right);    return min_dif;}