Accepted C Solution using Morris Traversal


  • 0
    R

    it's the stackless iterative solution.basic idea is that making links in the left branch's rightest child,which is the inorder precessor of the current node.restore it when iterate back.here is some excellent explanation far better than me.just check it out if u cant figure it out at first. it does cost me some time. http://stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

    int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    	int buff[255];
    	*returnSize=0;
    	struct TreeNode *cur=root;
    	struct TreeNode *prev=NULL;
    	while(cur){
    		if(cur->left){
    			prev=cur->left;
    			while(prev->right && prev->right!=cur)
    				prev=prev->right;
    
    			if(prev->right){
    				// just come from precessor
    				prev->right=NULL;
    				buff[*returnSize]=cur->val;
    				++(*returnSize);
    				cur=cur->right;
    			}else{
    				prev->right=cur;
    				cur=cur->left;
    			}
    
    		}else{
    			buff[*returnSize]=cur->val;
    			++(*returnSize);
    			cur=cur->right;
    		}
    	}
    	int bs=sizeof(int)*(*returnSize);
    	int *res=malloc(bs);
    
    	memcpy(res,buff,bs);
    	return res;
    }

Log in to reply
 

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