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.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
            return list;
        private void moveLeft(Stack<TreeNode> stack, TreeNode root) {
            while (root != null) {
                if (root.right != null) { // push right child in if any
                root = root.left;

Log in to reply

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