Practice/Meta/Leetcode 94. Binary Tree Inorder Traversal

Leetcode 94. Binary Tree Inorder Traversal

CodingMust

Problem

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

In postorder traversal, you visit nodes in this order:

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the current node

While a recursive solution is straightforward, can you implement this iteratively using an explicit stack?

Requirements

1. Return a list of integers representing node values in postorder sequence
2. Handle empty trees (return an empty list)
3. Consider both recursive and iterative approaches

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100
• Aim for O(n) time complexity where n is the number of nodes
• Can you solve it iteratively with O(h) space where h is tree height?

Examples

Example 1:

Input: root = [1, null, 2, 3] Tree structure: 1 \ 2 / 3 Output: [3, 2, 1] Explanation: Visit left child of 2 (which is 3), then node 2, then root 1

Example 2:

Input: root = [] Output: [] Explanation: Empty tree has no nodes to traverse

Example 3:

Input: root = [1] Output: [1] Explanation: Single node is visited once

Example 4:

Input: root = [1, 2] Tree structure: 1 / 2 Output: [2, 1] Explanation: Visit left child 2 first, then root 1