[Leetcode 94] Binary Tree Inorder Traversal

Description:

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]

Example 2:

Input: root = []
Output: []

Example 3:

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

Example 4:

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

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* inorderTraversal(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 = inorderTraversal(root->left, &left_size);
}
//search right
if(root->right){
right_arr = inorderTraversal(root->right, &right_size);
}

// add up the size
*returnSize = 1 + left_size + right_size;

int *res = (int*)malloc((*returnSize) * sizeof(int));

// assign the elements
int res_idx = 0;
// assign left
for(int i=0; i<left_size; i++, res_idx++){
res[res_idx] = left_arr[i];
}
// assign current
res[res_idx++] = root->val;
//assign right
for(int i=0; i<right_size; i++, res_idx++){
res[res_idx] = right_arr[i];
}

return res;
}

Explanation:

利用遞迴,先盡力往左邊找,左邊的會return形成一個array,再盡力的往右邊找,右邊的會形成一個array,最後再按照Inorder順序把它組合在一起。

C code solution (iterative):

int* inorderTraversal(struct TreeNode* root, int* returnSize){
// boundary
if(!root){
*returnSize = 0;
return NULL;
}

//init
struct TreeNode* buffer[100];
int res_size = 0;
struct TreeNode* stack[100];
stack[0] = root;
int stack_size = 1;

//main
while(stack_size){
// curr points to the last position of stack
struct TreeNode* curr = stack[stack_size-1];
// search left to the end
while(curr->left){
// check if the left node has already in buffer
for(int i=0; i<res_size; i++){
if(buffer[i] == curr->left){
goto LEFT_COMPLETE;
}
}
curr = curr->left;
stack[stack_size] = curr;
stack_size++;
}
LEFT_COMPLETE:
// pop the element from stack and place to buffer
curr = stack[stack_size-1];
stack[stack_size-1] = NULL;
stack_size--;
buffer[res_size] = curr;
res_size++;
//search one step to the right
if(curr->right){
stack[stack_size] = curr->right;
stack_size++;
}
}

// 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來模擬recurdion的行為。一開始先將root push進stack,接著用一個迴圈一直確認stack是否還有資料。在迴圈中,每一次先看stack的最後一個node(用指標curr指著),接著針對curr一直向左探索,每次探索到的node都塞進stack中,此外,探索前要確認左邊的node是否有走過,最後會走到最左邊的node,然後跳出迴圈。接著從stack中pop一個node,將這個node放到buffer中。然後如果右邊有node,將右邊一個node放進stack中。持續這樣的事情直到stack為空,最後將資料從buffer放進res。

Hi I am Samuel