my solution using no-recursive in-order binary tree iteration


  • 0
    F
    class Solution {
    public:
        int getMinimumDifference(TreeNode* root) {
            if (! root) return 0;
            int res = INT_MAX;
            stack<TreeNode *> st;
            int last = -1;
            TreeNode *p = root;
            while (p || !st.empty()) {
                while (p) {st.push(p); p=p->left;}
                if (!st.empty()) {
                    p = st.top();
                    if (last != -1) res = min(res, p->val-last);
                    last=p->val;
                    st.pop();
                    p = p->right;
                }
            }
            return res;
        }
    };
    

    It's very straightforward. when we in-order iterate a BST, we get the ascending array and the minimum difference must be between two subsequent elements. Use "last" to record the previous element and calculate the difference.


Log in to reply
 

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