Right first in-order Morris traversal solution O(n) : O(1)


  • 0
    W
    class Solution {
    public:
        TreeNode* convertBST(TreeNode* root) {
            TreeNode *curr = root, *prev = NULL;
    		int sum = 0, index = 0;
    		while(curr)
    		{
    			if(curr->right == NULL)
    			{
    				curr->val += sum;
    				sum = curr->val;
    				++index;
    				curr = curr->left;
    			}
    			else
    			{
    				prev = curr->right;
    				while(prev->left && prev->left != curr) prev = prev->left;
    				if(prev->left == NULL)
    				{
    					prev->left = curr;
    					curr = curr->right;
    				}
    				else
    				{
    					prev->left = NULL;
    					++index;
    					curr->val += sum;
    					sum = curr->val;
    					curr = curr->left;
    				}
    			}
    		}
    		return root;
        }
    };
    

Log in to reply
 

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