[数据结构与算法]94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点?root?，返回它的?中序?遍历。

示例

示例 1：

输入： root = [1,null,2,3]
输出： [1,3,2]

示例 2：

输入： root = []
输出： []

实现

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void Visited(struct TreeNode *root, int *res, int *index)
{
    if (root == NULL) {
        return;
    }
    Visited(root->left, res, index);
    res[*index] = root->val;
    (*index)++;
    Visited(root->right, res, index);
    return;
}

int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    int *res = (int*)malloc(sizeof(int) * 100);
    if (res == NULL) {
        printf("malloc space fail!!!\n");
        return NULL;
    }
    memset(res, 0, sizeof(int) * 100);
    *returnSize = 0;

    // 这里用returnSize作为要赋值的下标
    Visited(root, res, returnSize);

    return res;
}

方法二：非递归

int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    int *res = (int*)malloc(sizeof(int) * 100);
    if (res == NULL) {
        printf("malloc space fail!!!\n");
        return NULL;
    }
    memset(res, 0, sizeof(int) * 100);
    *returnSize = 0;

    struct TreeNode *cur = root;
    // 模拟栈
    struct TreeNode **stk = malloc(sizeof(struct TreeNode*) * 100);
    int top = -1;    // 当前栈顶元素的位置
    while (cur != NULL || top >= 0) {
        while (cur != NULL) {
            stk[++top] = cur;
            cur = cur->left;
        }
        cur = stk[top--];
        res[(*returnSize)++] = cur->val;
        cur = cur->right;
    }
    
    return res;
}