[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。

Hi I am Samuel