[Leetcode 144] Binary Tree Preorder Traversal

Description:

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

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

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

C code solution (recursive):

/**
 * 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().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //boundary
    if(!root){
        *returnSize = 0;
        return NULL;
    }
    
    //init
    int *left_arr, *right_arr;
    int left_size = 0, right_size = 0;
    
    //main
    //search left
    if(root->left)
        left_arr = preorderTraversal(root->left, &left_size);
    //search right
    if(root->right)
        right_arr = preorderTraversal(root->right, &right_size);
    
    //define the size
    *returnSize = 1 + left_size + right_size;
    
    //form the array
    int *res = (int*)malloc((*returnSize) * sizeof(int));
    int res_idx = 0;
    //insert the root
    res[res_idx] = root->val;
    res_idx++;
    //insert the left subtree
    for(int i=0; i<left_size; i++, res_idx++){
        res[res_idx] = left_arr[i];
    }
    //insert the right subtree
    for(int i=0; i<right_size; i++, res_idx++){
        res[res_idx] = right_arr[i];
    }
    
    return res;
}

Explanation:

運用recursion，若左邊不為空，先找左邊的樹return左邊數的preorder，若右邊不為空，再找右邊的樹的preorder，最後按照preorder的順序串接成res。

C code solution (iterative):

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //boundary
    if(!root){
        *returnSize = 0;
        return NULL;
    }
    
    //init
    struct TreeNode* stack[100];
    struct TreeNode* buffer[100];
    stack[0] = root;
    int stack_size = 1;
    int res_size = 0;
    
    //main
    while(stack_size){
        // pop the last element from stack
        struct TreeNode* curr = stack[stack_size-1];
        stack[stack_size-1] = NULL;
        stack_size--;
        //assign the element to the buffer
        buffer[res_size] = curr;
        res_size++;
        //place the right child to stack
        if(curr->right){
            stack[stack_size] = curr->right;
            stack_size++;
        }
        if(curr->left){
            stack[stack_size] = curr->left;
            stack_size++;
            curr = curr->left;
        }
    }
    
    //transfer the data from buffer to res
    int *res = (int*)malloc(res_size * sizeof(int));
    for(int i=0; i<res_size; i++){
        res[i] = buffer[i]->val;
    }
    *returnSize = res_size;
    
    return res;
}

Explanation:

運用一個stack。先將root放進stack，然後開始迴圈只要stack不為空。在迴圈中，先從stack中pop出一個元素，將其放到buffer中，接著如果右邊有node則將它放進stack，然後左邊有node再將它放進stack。等迴圈結束，將資料從buffer轉移到res，最後return res。