Share my simple neat CPP solution (0 ms)--use stack, without changing tree,easy to understand


  • 7
    T
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> result;
        if (!root) return result;	
        stack<TreeNode *> stk;
        stk.push(root);
        TreeNode *pre = root;
        while (!stk.empty())
        {
        	TreeNode *i_root = stk.top();
        	if (i_root->left && i_root->left != pre && i_root->right != pre)
        	{
        		stk.push(i_root->left);			//push left child
        	}
        	else if (i_root->right && i_root->right != pre)
        	{	
        		stk.push(i_root->right);		//push right child
        	}
        	else
        	{
        		result.push_back(i_root->val);	//record root
        		pre = stk.top();
        		stk.pop();						//stack pop
        	}
        }
        return result;
    }

  • 0
    T
    /**
    *
    * equivalent to the recursive one below in stack behaviour
    *
    * postorderTraversal(TreeNode *root)
    * {
    *		postorderTraversal(root->left); //push left child
    * 		postorderTraversal(root->right);//push right child
    *		record root->val;               //record root
    *		return;							//return cause stack pop
    * }
    */

Log in to reply
 

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