Share my AC code without reversing preorder traversal, one stack, one Hashset, O(n)


  • 1
    W

    Share my AC non-reverse preorder method

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            //base case
            if(root == null) return res;
            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            //store which node we have already printed out
            Set<TreeNode> set = new HashSet<TreeNode>();
            //for the corner case: 1 <- root -> null
            set.add(null);
            stack.offer(root);
            while(!stack.isEmpty()) {
                TreeNode cur = stack.peekFirst();
                //if node's subtrees are already printed out or it is a leaf node
                if((cur.left == null && cur.right == null) || (set.contains(cur.left) && set.contains(cur.right))) {
                    res.add(cur.val);
                    set.add(stack.pollFirst());
                }
                else {
                    if(cur.right != null) {
                        stack.offerFirst(cur.right);
                    }
                    if(cur.left != null) {
                        stack.offerFirst(cur.left);
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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