Runtime Error when try to do it iteratively


  • 0
    F

    I try this code on VS, It works well as there is no looping errors or something else, but for leetcode, it gives me the runtime-error, with the sample:"Last executed input: {3,1,#,#,2}", I don't know which part goes wrong. Plz help me!

    vector<int> postorderTraversal(TreeNode *root) {
    
    	vector<int> retVec;
    
    	if (root == NULL)
    		return retVec;
    	
    	TreeNode *pCur = root;
    	while (pCur != NULL)
    	{
    		retVec.insert(retVec.begin(),pCur->val);
    		if (pCur->left == NULL)
    			pCur = pCur->right;
    		else
    		{
    			if (pCur->right == NULL)
    				pCur = pCur->left;
    			else
    			{
    				TreeNode *pRightLeft = pCur->right;
    				while (pRightLeft->left != NULL)
    					pRightLeft = pRightLeft->left;
    				
    				pRightLeft->left = pCur->left;
    				pCur = pCur->right;
    			}
    		}
    	}
    	return retVec;
    }

  • 1
    P

    I must say, you are doing it in the wrong way.

    retVec.insert(retVec.begin(),pCur->val); will take O(N) time to complete and you algorithm is basically O(N^2)


Log in to reply
 

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