145. Binary Tree Postorder Traversal

Description

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

Constraints

• The number of the nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

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]

Example 4

Input: root = [1, 2]

Output: [2, 1]

Example 5

Input: root = [1, null, 2]

Output: [2, 1]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : O(N), where N is the number of nodes. We visit each 
 *    node exactly once, thus the time complexity is O(N).
 * Space complexity : up to O(H) to keep the recursion stack, 
 *    where H is a tree height.
 */
 
 class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList();
        helper(root, result);
        return result;
    }
    
    private void helper(TreeNode node, LinkedList<Integer> result) {
        if(node == null) return;
        helper(node.left, result);
        helper(node.right, result);
        result.add(node.val);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> resultList = new LinkedList();
        Stack<TreeNode> s = new Stack();
        TreeNode curr = root;
        while(!s.isEmpty() || curr != null) {
            if(curr != null) {
                s.push(curr);
                curr = curr.left;
            } else {
                TreeNode temp = s.peek().right;
                if(temp == null) {
                    temp = s.pop();
                    resultList.add(temp.val);
                    while(!s.isEmpty() && temp == s.peek().right) {
                        temp = s.pop();
                        resultList.add(temp.val);
                    }
                } else {
                    curr = temp;
                }
            }
        }
        return resultList;
    }
}

Solution 3

/**
 * Time complexity : O(N), where N is the number of nodes. We visit each 
 *    node exactly once, thus the time complexity is O(N).
 * Space complexity : up to O(H) to keep the stack, where H is a tree height.
 */

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList();
        
        if(root == null) return result;
        
        Stack<TreeNode> stack = new Stack();
        stack.add(root);
        
        while(!stack.isEmpty()) {
            root = stack.pop();
            result.addFirst(root.val);
            if(root.left != null) stack.push(root.left);
            if(root.right != null) stack.push(root.right);
        }
        
        return result;
    }
}

Follow up