[Leetcode 145] Binary Tree Postorder Traversal

Description:

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

Example 1:

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

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: [2,1]

Constraints:

  • The number of the 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* postorderTraversal(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 = postorderTraversal(root->left, &left_size);
//search right
if(root->right)
right_arr = postorderTraversal(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 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];
}
//insert the root
res[res_idx] = root->val;

return res;
}

Explanation:

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

C code solution:

int* postorderTraversal(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){
struct TreeNode* curr = stack[stack_size-1];

//place the right child to stack
if(curr->right){
//check if the node is already in buffer
for(int i=0; i<res_size; i++){
if(curr->right == buffer[i])
goto COMPLETE;
}
stack[stack_size] = curr->right;
stack_size++;
}
if(curr->left){
//check if the node is already in buffer
for(int i=0; i<res_size; i++){
if(curr->left == buffer[i])
goto COMPLETE;
}
stack[stack_size] = curr->left;
stack_size++;
curr = curr->left;
}
if(!curr->right && !curr->left){
COMPLETE:
// pop the last element from stack
stack[stack_size-1] = NULL;
stack_size--;
//assign the element to the buffer
buffer[res_size] = curr;
res_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。先將root放進stack,然後開始迴圈只要stack不為空。在迴圈中,先看右邊有沒有node,有node則將它放進stack,接著看左邊有沒有node,左邊有node再將它放進stack。最後check如過這個node都沒有child nodes,將其放到buffer中。等迴圈結束,將資料從buffer轉移到res,最後return res。

微幅的改變:若left node或right node已放進stack,我們便將 curr->left, curr->right 設為NULL。這樣可以防止之後已經檢查過的child node再次被放進stack中

C code solution (iterative revision):

int* postorderTraversal(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){
struct TreeNode* curr = stack[stack_size-1];

if(!curr->right && !curr->left){
// pop the last element from stack
stack[stack_size-1] = NULL;
stack_size--;
//assign the element to the buffer
buffer[res_size] = curr;
printf("assign number: %d\n", curr->val);
res_size++;
}else{
//place the right child to stack
if(curr->right){
printf("go right\n");
stack[stack_size] = curr->right;
stack_size++;
curr->right = NULL;
}
if(curr->left){
printf("go left\n");
stack[stack_size] = curr->left;
stack_size++;
curr->left = NULL;
}
}

}

//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;
}

Hi I am Samuel