My accepted JAVA solution


  • 10
    P

    Straightforward thought:
    You will meet a node three times from a stack.
    For the first time, push the left. The second time, push the right, The third time you meet it, move it to result.

    class TreeNodeStack {
    	TreeNode node;
    	int count;
    
    	TreeNodeStack(TreeNode node) {
    		this.node = node;
    	}
    }
    
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> result = new ArrayList<Integer>();
    	Deque<TreeNodeStack> stack = new ArrayDeque<TreeNodeStack>();
    	stack.add(new TreeNodeStack(root));
    	while (stack.size() > 0) {
    		TreeNodeStack s = stack.peekLast();
    		s.count++;
    		if (s.node == null) {
    			stack.pollLast();
    		}
    		else if(s.count==1){
    			stack.add(new TreeNodeStack(s.node.left));
    		}
    		else if(s.count==2){
    			stack.add(new TreeNodeStack(s.node.right));
    		}
    		else if (s.count == 3) {
    			stack.pollLast();
    			result.add(s.node.val);
    		}
    	}
    	return result;
    }

  • 0
    C

    your code is perfect good by using extra ds


  • 1
    M

    Inspired by peterdyf, thanks!

    public List<Integer> postorderTraversal(TreeNode root) {
        /**
         * Write out a recursive version
         * Then try to translate it to iterative version.
         *
         * Translate process :
         * When a method is called, we push a function frame into callStack
         * After the method finishes, we pop the function frame out.
         *
         * line1 visit(root.left) if root.left is not null
         * line2 visit(root.right) if root.right is not null
         * line3 visit(root)
         */
    
        List<Integer> postOrder = new ArrayList<Integer>();
    
        if (root == null) {
            return postOrder;
        }
    
        Stack<FunctionFrame> callStack = new Stack<FunctionFrame>();
        callStack.push(new FunctionFrame(root));
    
        while (!callStack.isEmpty()) {
            FunctionFrame curFrame = callStack.peek();
    
            if (curFrame.programCounter == 1) {
                if (curFrame.treeNode.left != null) {
                    callStack.push(new FunctionFrame(curFrame.treeNode.left));
                }
            } else if (curFrame.programCounter == 2) {
                if (curFrame.treeNode.right != null) {
                    callStack.push(new FunctionFrame(curFrame.treeNode.right));
                }
            } else if (curFrame.programCounter == 3) {
                postOrder.add(curFrame.treeNode.val);
            } else {
                callStack.pop();
            }
    
            curFrame.programCounter++;
        }
    
        return postOrder;
    }
    
    public class FunctionFrame {
        public TreeNode treeNode;
        // programCounter == 1 means visit(root.left) is calling
        public int programCounter;
    
        public FunctionFrame(TreeNode treeNode) {
            this.treeNode = treeNode;
            /**
             * When a new function frame is created,
             * we move program counter to its first line, meaning first line is calling
             */
            this.programCounter = 1;
        }
    }

  • 0
    G

    You can use Stack instead of Deque, because you don't need to operate at the two ends.


  • 0
    P

    Thanks. I used to use Stack but Java Docs say Deque interface and its implementations should be used in preference to Stack


Log in to reply
 

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