leetcode 530. Minimum Absolute Difference in BST | inorder

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
    /
   2

Output:
1

Explanation:
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;
}