Accepted C solution using Morris Traversal


  • 0
    R

    another modification transform it into postorder traversal.the difference between inorder implement is that when iterate back it requires to reverse the values of the left branch's right branch. below is inorder and preorder solutions,maybe it's easier to figure it out gradually.it dose is complex.


    preorder: https://leetcode.com/discuss/44194/accepted-c-solution-using-morris-traversal
    inorder: https://leetcode.com/discuss/44150/accepted-c-solution-using-morris-traversal


    int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    	int buff[255];
    	*returnSize=0;
    	struct TreeNode dump;
    	dump.left=root;
    	dump.right=NULL;
    	dump.val=0;
    	struct TreeNode *cur=&dump;
    	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
    				struct TreeNode *p=cur->left;
    				int rn=0;
    				while(p!=cur){
    					buff[*returnSize]=p->val;
    					++(*returnSize);
    					p=p->right;
    					++rn;
    				}
    				//reverse right branch vals
    				int pt=*returnSize -1;
    				int ph=(*returnSize -rn);
    				while(pt>ph){
    					int tmp=buff[ph];
    					buff[ph]=buff[pt];
    					buff[pt]=tmp;
    					--pt;
    					++ph;
    				}
    				prev->right=NULL;
    				cur=cur->right;
    			}else{
    				prev->right=cur;
    				cur=cur->left;
    			}
    
    		}else{
    			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.