Easy Iterative Java solution with O(logn) stack space


  • 0
    L
        public List<Integer> postorderTraversal(TreeNode root) {
            //{1,#,2,3},->321
            if(root==null) {
                return Collections.EMPTY_LIST;
            }
            List<Integer> list = new ArrayList<>();
            Stack<TreeNodeWrapper> stack = new Stack<>();
            stack.push(new TreeNodeWrapper(root));
            while(!stack.isEmpty()) {
                //get the root and mark it visited.
                TreeNodeWrapper marker = stack.peek();
                if(marker.isVisited()) {
                    list.add(marker.root.val);
                    stack.pop();
                }
                else {
                    TreeNode right = marker.root.right;
                    if(right!=null) {
                        stack.push(new TreeNodeWrapper(right));
                    }
                    TreeNode left = marker.root.left;
                    if(left!=null) {
                        stack.push(new TreeNodeWrapper(left));
                    }
                    marker.markVisited();
                }
            }
            return list;
        }
        
        private static class TreeNodeWrapper {
            private TreeNode root;
            private boolean isVisited;
            
            TreeNodeWrapper(TreeNode root) {
                this.root = root;
            }
            
            void markVisited() {
                isVisited=true;
            }
            
            boolean isVisited() {
                return isVisited;
            }
        }
    

Log in to reply
 

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