145. Binary Tree Postorder Traversal

Easy

Problem Description

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

Examples

Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    
    result = []
    stack = [(root, False)]
    
    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    
    return result

Java Solution


class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack> stack = new Stack<>();
        stack.push(new Pair<>(root, false));
        
        while (!stack.isEmpty()) {
            Pair pair = stack.pop();
            TreeNode node = pair.getKey();
            boolean visited = pair.getValue();
            
            if (visited) {
                result.add(node.val);
            } else {
                stack.push(new Pair<>(node, true));
                if (node.right != null) {
                    stack.push(new Pair<>(node.right, false));
                }
                if (node.left != null) {
                    stack.push(new Pair<>(node.left, false));
                }
            }
        }
        
        return result;
    }
}

C++ Solution


class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector result;
        if (!root) {
            return result;
        }
        
        stack> stack;
        stack.push({root, false});
        
        while (!stack.empty()) {
            auto [node, visited] = stack.top();
            stack.pop();
            
            if (visited) {
                result.push_back(node->val);
            } else {
                stack.push({node, true});
                if (node->right) {
                    stack.push({node->right, false});
                }
                if (node->left) {
                    stack.push({node->left, false});
                }
            }
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    if (!root) {
        return [];
    }
    
    const result = [];
    const stack = [[root, false]];
    
    while (stack.length > 0) {
        const [node, visited] = stack.pop();
        
        if (visited) {
            result.push(node.val);
        } else {
            stack.push([node, true]);
            if (node.right) {
                stack.push([node.right, false]);
            }
            if (node.left) {
                stack.push([node.left, false]);
            }
        }
    }
    
    return result;
};

C# Solution


public class Solution {
    public IList PostorderTraversal(TreeNode root) {
        IList result = new List();
        if (root == null) {
            return result;
        }
        
        Stack<(TreeNode node, bool visited)> stack = new Stack<(TreeNode, bool)>();
        stack.Push((root, false));
        
        while (stack.Count > 0) {
            var (node, visited) = stack.Pop();
            
            if (visited) {
                result.Add(node.val);
            } else {
                stack.Push((node, true));
                if (node.right != null) {
                    stack.Push((node.right, false));
                }
                if (node.left != null) {
                    stack.Push((node.left, false));
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Solution Explanation

This solution uses an iterative approach with a stack and visited flag:

Key points: