Correct and efficient O(n) iterative solution using Stack of Lists


  • 0
    S

    Here is my approach:

    • Create a stack of lists.
    • Starting from root, push the list left->right->root to the stack
    • Pop from the stack, remove the first element of the list. If the list becomes empty, add the element to the result list. Else, create a new list as left->right->current and add it to the stack.
    • Repeat until stack is empty.
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            Stack <LinkedList<TreeNode>> stack = new Stack<LinkedList<TreeNode>>();
            LinkedList<Integer>  resultList = new LinkedList<>();
            if(root == null) return resultList;
            LinkedList<TreeNode> list = new LinkedList<>();
            if(root.left != null) list.add(root.left);
            if(root.right != null) list.add(root.right);
            list.add(root);
            stack.push(list);
            while(!stack.empty()) {
                LinkedList<TreeNode> currList = stack.pop();
                TreeNode curr = currList.remove();
                if(currList.isEmpty()) {
                    resultList.add(curr.val);
                } else {
                    stack.push(currList);
                    LinkedList<TreeNode> tempList = new LinkedList<>();
                    if(curr.left != null) tempList.add(curr.left);
                    if(curr.right != null) tempList.add(curr.right);
                    tempList.add(curr);
                    stack.push(tempList);
                }
            }
            return resultList;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.