tags: leetcode easy Stack Tree Depth-First Search Binary Tree

94. Binary Tree Inorder Traversal

Description

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Examples

Example1

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• $-100 \leq Node.val \leq 100$

Code

void inorder(int* returnList, struct TreeNode* root, int* returnSize) {
    if (root == NULL)
        return 0;
    inorder(returnList, root->left, returnSize);
    returnList[(*returnSize)++] = root->val;
    inorder(returnList, root->right, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* returnList = malloc(100 * sizeof(int));
    inorder(returnList, root, returnSize);
    return returnList;
}

Complexity

Space	Time
$O(1)$	$O(N)$

Result

• Runtime : 0 ms, 100%
• Memory : 5.8 MB, 69.82%