Accepted C Solution using Morris Traversal


  • 0
    R

    the Morris Traversal Algorithm is implemented as inorder traversal typically.a little modification will make it work. the inorder problem solution is here. https://leetcode.com/discuss/44150/accepted-c-solution-using-morris-traversal

    int* preorderTraversal(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;
    				cur=cur->right;
    			}else{
    				prev->right=cur;
    				buff[*returnSize]=cur->val;
    				++(*returnSize);
    				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.