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 the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach 01:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversePostorder(root, result);
        return result;
    }

private:
    void traversePostorder(TreeNode* node, vector<int>& result) {
        if (node == nullptr)
            return;

        traversePostorder(node->left, result);
        traversePostorder(node->right, result);
        result.push_back(node->val);
    }
};

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.traversePostorder(root, result)
        return result

    def traversePostorder(self, node, result):
        if node is None:
            return

        self.traversePostorder(node.left, result)
        self.traversePostorder(node.right, result)
        result.append(node.val)

Time Complexity

• Traversal:

  The function traverses each node of the binary tree exactly once. Since there are \( n \) nodes in the tree, the time complexity is \( O(n) \).

Space Complexity

• Recursive Call Stack:

  In the worst case (for a skewed tree), the depth of the recursion stack can go up to \( O(n) \). For a balanced tree, the depth of the recursion stack would be \( O(\log n) \).

• Result Vector:

  The result vector stores the values of all nodes, requiring \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), considering the worst-case space usage of the recursion stack and the result vector.