C++_BST - Inorder Traverse


  • 0

    Just an in-order traverse problem, because for each tree node, the closest value is either from its pre-node or successor node.

    class Solution {
    public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX;
        if(root == nullptr) return res;
        stack<TreeNode*> sk;
        TreeNode* pre = nullptr;
        TreeNode* suc = nullptr;
        while(true){
            while(root){
                sk.push(root);
                root = root->left;
            }
            if(sk.empty()) break;
            root = sk.top();
            sk.pop();
            suc = (!sk.empty()) ? sk.top() : nullptr;
            if(pre){
                res = min(res, abs(root->val - pre->val));
            }
            if(suc){
                res = min(res, abs(root->val - suc->val));
            }
            pre = root;
            root = root->right;
        }
        return res;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.