Java "real" postorder one stack straightforward O(n) space and time


  • 0

    Unlike most of posts which esentially does preorder and a reverse order of linkedlist.

    This is real postorder. The nodes printed in real postorder. We use only one stack.

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            moveLeft(stack, root);
            while (!stack.isEmpty()) {
                root = stack.pop();
                if (!stack.isEmpty() && root.right == stack.peek()) {
                    stack.pop(); 
                    stack.push(root); // push root back into stack
                    moveLeft(stack, root.right); //moveLeft its right substree
                } else { // no right child or right child not equal to top of stack
                    list.add(root.val);
                }
            }
            return list;
        }
        
        private void moveLeft(Stack<TreeNode> stack, TreeNode root) {
            while (root != null) {
                if (root.right != null) { // push right child in if any
                    stack.push(root.right);
                }
                stack.push(root);
                root = root.left;
            }
        }
    }

Log in to reply
 

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