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