# [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:

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:

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