LeetCode 94. 二叉树的中序遍历（C语言）

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法一: 采用递归算法，按照左根右的顺序遍历二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * 定义一个数组res用来存储遍历的节点,
 * 其中returnSize 使用来储存当前数组位置的， 
 * returnSize 即为当前位置
 */
void inorder(struct TreeNode* root, int* returnSize, int* res){
    if(root != NULL){
        inorder(root->left, returnSize, res);
        res[(*returnSize)++] = root->val;
        inorder(root->right, returnSize, res);
    }
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(sizeof(int)*1000);
    *returnSize = 0;
    inorder(root, returnSize, res);
    return res;
}

方法二: 采用非递归算法，不定义栈结构，而是利用一个数组和指针模拟栈操作

 int* inorderTraversal(struct TreeNode* root, int* returnSize) {
     int *res = (int*)malloc(sizeof(int)*1000);
     struct TreeNode* stack[1000];
     int top = -1; //栈顶指针
     int size = 0;
     while(root || top != -1) {
         while(root != NULL){
             stack[++top] = root;  //进栈操作
             root = root->left;
         }
        if(top != -1){
            root = stack[top--];  //出栈操作
            res[size++] = root->val; //访问当前结点
            root = root->right;
        }
     }
    *returnSize = size;
     return res;
 }

方法三: 采用非递归算法，定义栈结构及其相应的方法，进而进行操作。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct stack *Stack;
typedef struct node *Node;
struct stack
{
    Node top;
};
struct node
{
    Node next;
    struct TreeNode *n;
};
void push(Stack s,struct TreeNode *n1)
{
    Node a=(Node)malloc(sizeof(*a));
    a->n=n1;
    a->next=s->top;
    s->top=a;
}
struct TreeNode *pop(Stack s)
{
    struct TreeNode *a=s->top->n;
    s->top=s->top->next;
    return a;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res=(int*)malloc(10000*sizeof(int));
    *returnSize=0;
    
    Stack s=(Stack)malloc(sizeof*s);
    s->top=NULL;
    
    struct TreeNode *k=root;
    while(s->top||k)
    {
        if(k)
        {
            push(s,k);
            k=k->left;
        }
        else 
        {
            k=pop(s);
            res[(*returnSize)++]=k->val;
            k=k->right;
        }
    }
    return res;
}