# Very typical solution using one stack in C, accepted as best

• #define LEN 1000
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
*returnSize = 0;
if(!root) return NULL;
int* arr = (int*)malloc(sizeof(int)*LEN);
struct TreeNode **stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*LEN);
int top = -1;
stack[++top] = root;
struct TreeNode *pre = NULL;
while(top > -1)
{
struct TreeNode *cur = stack[top];
if(!pre || pre->left==cur || pre->right==cur)
{
if(cur->left) stack[++top] = cur->left;
else if(cur->right) stack[++top] = cur->right;
else arr[(*returnSize)++] = cur->val, top--;
}
else if(cur->left == pre)
{
if(cur->right) stack[++top] = cur->right;
else arr[(*returnSize)++] = cur->val, top--;
}
else if(cur->right == pre)
arr[(*returnSize)++] = cur->val, top--;
pre = cur;
}
return arr;
}

• Corresponding C++ version

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
if(!root) return vector<int>();
stack<TreeNode*> node_stack;
vector<int> v;
node_stack.push(root);
TreeNode *pre = NULL, *cur = NULL;
while(!node_stack.empty())
{
cur = node_stack.top();
if(!pre || pre->left==cur || pre->right==cur)
{
if(cur->left) node_stack.push(cur->left);
else if(cur->right) node_stack.push(cur->right);
else { v.push_back(cur->val); node_stack.pop(); }
}
else if(cur->left == pre)
{
if(cur->right) node_stack.push(cur->right);
else { v.push_back(cur->val); node_stack.pop(); }
}
else if(cur->right == pre)
{
v.push_back(cur->val);
node_stack.pop();
}
pre = cur;
}
return v;
}
};

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