145. Binary Tree Postorder Traversal

Binary Tree Postorder Traversal - LeetCode

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]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

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

Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

• Recursively traverse the left subtree.
• Recursively traverse the right subtree.
• Store the root element.

class Solution {
    public void traversal(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;
        if (root.left != null)
            traversal(root.left, ans);
        if (root.right != null)
            traversal(root.right, ans);
        ans.add(root.val);
}
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        traversal(root, ans);
        return ans;
    }
}

Time Complexity: O(N)
Auxiliary Space: O(H), where H is the height of the tree.

Solution 2: Iterative — Using 2 stacks

• Create 2 stacks of TreeNode, push root Node to stack1.
• Do the following till stack1 is not empty:

1. Pop a Node from the stack and push it to stack2.
2. If the left child is not null, push it to the stack1.
3. If the right child is not null, push it to the stack1.

• Iterate over stack2 and add the current node value to the list.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if (root == null)
            return ans;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode current = stack1.pop();
            stack2.push(current);
            if (current.left != null)
                stack1.push(current.left);
            if (current.right != null)
                stack1.push(current.right);
        }
        while (!stack2.isEmpty()) {
            TreeNode current = stack2.pop();
            ans.add(current.val);
        }
        return ans;
    }
}

Time Complexity: O(N)
Space: O(H), where H is the height of the tree.

Solution 3: Iterative — Using 1 stack

• Create a stack of TreeNode and push root to it.
• Do the following till stack is not empty:
• Pop a Node from the stack and add it to the start of list(ans), use linked list.
• If the left child is not null, push it to the stack.
• If the right child is not null, push it to the stack.

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

Time Complexity: O(N)
Space: O(H), where H is the height of the tree.