morris traverse


  • 0
    A
    class Solution {
    public:
        int getMinimumDifference(TreeNode* root) {
            int* last = nullptr;
            int ret = INT_MAX;
            while (root) {
                TreeNode* l = root->left;
                if (l) {
                    while (l->right && l->right != root) l = l->right;
                    if (l->right == root) {
                        l->right = nullptr;
                    } else {
                        l->right = root;    
                        root = root->left;
                        continue;
                    }
                }     
                if (last == nullptr) last = new int(root->val);
                else {
                    ret = min(ret, abs(root->val - *last));
                    *last = root->val;
                }
                root = root->right;
            }
            delete last;
            return ret;
        }
    };
    

Log in to reply
 

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