Description

94. Binary Tree Inorder Traversal

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

Example 1:

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

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 建立一個結果陣列，初始大小為 100（假設最大不超過 100 個節點）
    int* result = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;

    // 建立一個Stack來模擬遞歸，最大大小為 100
    struct TreeNode** stack = (struct TreeNode**)malloc(100 * sizeof(struct TreeNode*));
    int stackSize = 0;
    
    // 使用 current 指向當前節點
    struct TreeNode* current = root;

    // 開始迭代遍歷節點，當節點大小不為零
    while (current != NULL || stackSize > 0) {
        // 將當前節點的所有left node push到stack
        while (current != NULL) {
            stack[stackSize++] = current;
            current = current->left;
        }

        // 從stack中pop節點，處理該節點的值
        current = stack[--stackSize];
        result[(*returnSize)++] = current->val;

        // 繼續處理right subtree
        current = current->right;
    }

    // 釋放stack空間
    free(stack);

    return result;
}

Testing

#include <stdio.h>
#include <stdlib.h>

/**
 * 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().
 */
#include <stdio.h>
#include <stdlib.h>

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 建立一個結果陣列，初始大小為 100（假設最大不超過 100 個節點）
    int* result = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;

    // 建立一個Stack來模擬遞歸，最大大小為 100
    struct TreeNode** stack = (struct TreeNode**)malloc(100 * sizeof(struct TreeNode*));
    int stackSize = 0;
    
    // 使用 current 指向當前節點
    struct TreeNode* current = root;

    // 開始迭代遍歷節點，當節點大小不為零
    while (current != NULL || stackSize > 0) {
        // 將當前節點的所有left node push到stack
        while (current != NULL) {
            stack[stackSize++] = current;
            current = current->left;
        }

        // 從stack中pop節點，處理該節點的值
        current = stack[--stackSize];
        result[(*returnSize)++] = current->val;

        // 繼續處理right subtree
        current = current->right;
    }

    // 釋放stack空間
    free(stack);

    return result;
}


// 測試函數
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 測試函數
void testInorderTraversal() {
    // 構造測試用例 [1,null,2,3]
    struct TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->left = createNode(3);

    int returnSize;
    int* result = inorderTraversal(root, &returnSize);

    // 輸出結果
    printf("Inorder Traversal Result: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    // 釋放結果陣列
    free(result);
}

// 主函數
int main() {
    testInorderTraversal();
    return 0;
}