依次从root到最左边结点加入堆栈
push(s,node)
node = node->left
当加到node为空的时候，从堆栈弹出并保存之后依次再从最左边的右结点开始重复上面动作
struct Stack{
struct ListNode * dummy;
};
void push(struct Stack * s, int val)
{
struct ListNode * node = calloc(1, sizeof(struct ListNode));
node->val = val;
node->next = s->dummy->next;
s->dummy->next = node;
}
int pop(struct Stack *s)
{
struct ListNode * p = s->dummy->next;
if(p){
s->dummy->next = p->next;
int ret = p->val;
free(p);
return ret;
}else{
printf("empty stack\n");
return -1;
}
}
struct Stack * init_stack()
{
struct Stack *s;
s = calloc(1, sizeof(struct Stack));
s->dummy = calloc(1, sizeof(struct ListNode));
return s;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
struct Stack * s1 = init_stack();
//struct Stack * s2 = init_stack();
if(root == NULL)
return NULL;
//push(s1,(int)root);
*returnSize = 0;
int *ret = calloc(*returnSize, sizeof(int));
struct TreeNode * node = root;
while(s1->dummy->next != NULL || node != NULL){
if(node){
push(s1, node);
node = node->left;
}else{
node = (struct TreeNode *)pop(s1);
ret = realloc(ret, (*returnSize+1)*sizeof(int));
ret[*returnSize] = node->val;
*returnSize +=1;
node = node->right;
}
}
