Two Stacks Java Solution


  • 1

    Using an extra stack to remember all the explored TreeNode, so the next time we visit it, we add it to the result.

        public List<Integer> inorderTraversal(TreeNode root) {
            
            List<Integer> res = new ArrayList<>();
            if(root == null) {
                return res;
            }
            
            Deque<TreeNode> stack = new ArrayDeque<>();
            stack.push(root);
            
            Deque<TreeNode> roots = new ArrayDeque<>();
            
            
            while(!stack.isEmpty()) {
                
                TreeNode n = stack.pop();
                
                if(n == roots.peek()) {
                    
                    roots.pop();
                    res.add(n.val);
                } else {
                    
                    if(n.right != null) {
                        stack.push(n.right);
                    }
                    stack.push(n);
                    roots.push(n);
                    if(n.left != null) {
                        stack.push(n.left);
                    }                
                }
            }
            return res;
        }
    

  • 0
    A

    Good solution! I went with 2 stacks as well but ran into a lot of confusion with adding items to the "roots" stack, kept failing edge cases. Thanks for this explanation to help me understand better!


  • 0

    @abarganier Thank you : )


Log in to reply
 

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