leetcode: 94. 二叉树的中序遍历(C: 递归+迭代)

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

#define MAX_NUM 100
int *returnArray = NULL;

// 递归
void myInorderTraversal(struct TreeNode *root, int *returnSize)
{
    if (NULL == root) return;

    myInorderTraversal(root->left, returnSize);

    returnArray[*returnSize] = root->val;
    *returnSize += 1;

    myInorderTraversal(root->right, returnSize); 

    return;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    if (NULL == root) {
        return NULL;
    }

    returnArray = (int *)malloc(sizeof (int) * MAX_NUM);
    myInorderTraversal(root, returnSize);
    return returnArray;
}

迭代：栈

// 迭代， 考虑用栈存储遍历的节点
#define MAX_NUM 100

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    if (NULL == root) {
        return NULL;
    }

    int *returnArray = (int *)malloc(sizeof (int) * MAX_NUM);
    struct TreeNode *stack[MAX_NUM]  = {0};
    int top = -1;

    struct TreeNode *tmp = root;
    while (tmp || top >= 0) {
        // 当前节点左元素全部加入stack
        while (tmp) {
            stack[++top] = tmp;
            tmp = tmp->left;
        }

        // 将当前栈顶元素放入待返回的数组
        tmp = stack[top--];
        returnArray[(*returnSize)++] = tmp->val;

        //将右元素赋值给tmp
        tmp = tmp->right;   
    }

    return returnArray;
}