C++ solution using Morris Traversal O(n) + O(1)


  • 0
    W
    class Solution {
    public:
        int getMinimumDifference(TreeNode* root) {
    		int res = INT_MAX, nums[2] = {0, 0}, index = 0;
            TreeNode *curr = root, *prev = NULL;
    		while(curr != NULL)
    		{
    			if(curr->left == NULL)
    			{
    				nums[index % 2] = curr->val;
    				if(index > 0) res = min(res, nums[index % 2] - nums[(index + 1) % 2]);
    				++index;		    
    				curr = curr->right;
    			}
    			else
    			{
    				prev = curr->left;
    				while(prev->right != NULL && prev->right != curr) prev = prev->right;
    				if(prev->right == curr)
    				{
    					nums[index % 2] = curr->val;
    					if(index > 0) res = min(res, nums[index % 2] - nums[(index + 1) % 2]);
    					++index;
    					prev->right = NULL, curr = curr->right;
    				}
    				else
    				{
    					prev->right = curr, curr = curr->left;
    				}
    			}
    		}
    		return res;
        }
    };
    

Log in to reply
 

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