145. Binary Tree Postorder Traversal

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]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

From: LeetCode
Link: 145. Binary Tree Postorder Traversal

---

Solution:

Ideas:

1. Struct Definition: The TreeNode structure defines a binary tree node with val, left, and right pointers.

2. Helper Function: The postorderHelper function recursively traverses the tree in postorder (left, right, root) and fills the result array with node values.

3. Main Function:

• Allocates memory for the result array assuming a maximum of 100 nodes.
• Initializes returnSize to 0.
• Calls the helper function to fill the result array.
• Returns the result array.

Code:

/**
 * 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().
 */
void postorderHelper(struct TreeNode* root, int* result, int* returnSize) {
    if (root == NULL) {
        return;
    }
    
    // Traverse the left subtree
    postorderHelper(root->left, result, returnSize);
    
    // Traverse the right subtree
    postorderHelper(root->right, result, returnSize);
    
    // Visit the root node
    result[(*returnSize)++] = root->val;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    // Allocate memory for the result array
    int* result = (int*)malloc(100 * sizeof(int));  // Assuming the maximum number of nodes is 100
    
    // Initialize the return size to 0
    *returnSize = 0;
    
    // Perform the postorder traversal
    postorderHelper(root, result, returnSize);
    
    return result;
}