Simple java solution using Stack and Linked List


  • 0
    C

    Hello Mind Benders
    This is my first post in this site, I appreciate people posting their solutions, i have learned a lot from it. I see few others have solved this in similar fashion, but i would like to share how i came with solution.

    These problem poses good mental exercise. So much mind bending we have to do to come up with solutions.

    I solved Pre order traversal iteratively before this, but trying to follow that same approach didn't help here. I solved this problem by reverse engineering the solution of recursive solution of this problem for some examples, till then i was stuck. In addition to stack for TreeNode, either stack or linked list could be used to store val field list.

        public List<Integer> postorderTraversal(TreeNode r) {
            LinkedList<Integer> list = new LinkedList<>();
            if (r == null)
                return list;
    
            Stack<TreeNode> stack = new Stack<>();
            stack.push(r);
    
            while (!stack.isEmpty()) {
                final TreeNode treeNode = stack.pop();
                list.addFirst(treeNode.val);
                if (treeNode.left != null)
                    stack.push(treeNode.left);
                if (treeNode.right != null)
                    stack.push(treeNode.right);
            }
            return list;
        }
    
    

Log in to reply
 

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