145.c

#include<stdio.h>
#include<stdlib.h>

structTreeNode {
intval;
structTreeNode*left;
structTreeNode*right;
};

structStackNode {
structTreeNode*val;
structStackNode*next;
};

structStack {
structStackNode*top_pt;
intsize;
};

voidpush(structStack*stack, structTreeNode*new_data) {
if (stack) {
structStackNode*new_node
= (structStackNode*)calloc(1, sizeof(structStackNode));
new_node->val=new_data;
new_node->next=stack->top_pt;

stack->top_pt=new_node;
stack->size++;
 }
}

structTreeNode*top(structStackstack) {
if (stack.top_pt) {
returnstack.top_pt->val;
 }
elsereturnNULL;
}

voidpop(structStack*stack) {
if (stack&&stack->top_pt) {
structStackNode*top=stack->top_pt;
stack->top_pt=top->next;
stack->size--;
free(top);
 }
}

int*postorderTraversal(structTreeNode*root, int*returnSize) {
*returnSize=0;
if (root==NULL) returnNULL;

structStackstack;
stack.top_pt=NULL;
stack.size=0;

int*ret= (int*)calloc(1024, sizeof(int));
structTreeNode*p=root;
structTreeNode*last=NULL;
while (stack.size||p) {
if (p) {
push(&stack, p);
p=p->left;
 }
else {
structTreeNode*t=top(stack);
if (t->right&&last!=t->right) {
p=t->right;
 }
else {
pop(&stack);
ret[(*returnSize)++] =t->val;
last=t;
 }
 }
 }
returnret;
}

intmain() {
structTreeNode*t= (structTreeNode*)calloc(5, sizeof(structTreeNode));
structTreeNode*p=t;
p->val=4;

p->left=++t;
t->val=2;
p->left->left=++t;
t->val=1;
t->left=t->right=NULL;
p->left->right=++t;
t->val=3;
t->left=t->right=NULL;

p->right=++t;
t->val=5;
t->left=t->right=NULL;

intsize=0;
int*ret=postorderTraversal(p, &size);
inti;
/* should be 13254 */
for (i=0; i<size; i++) {
printf("%d", ret[i]);
 }
printf("\n");

return0;
}