A Simple and Easy-Understanding Interative Java Method with detailed comments.

  • 0

    The method does not use something like list.addFirst(), just simulates the process of PostOrderTraversal as possible as.

        public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> res = new ArrayList<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                //push period 
                while (cur != null) {
                    cur = cur.left;
                //we can't directly pop here, because the Node we will pop maybe has non-null right child.
                TreeNode top = stack.peek();
                if (top.right == null) { //It has null right child, so it's safe to pop the Node and access it now.
                    cur = stack.pop();
    //After accessing the Node top, there are two choices: 
    //1. one is we continue pop until we can't pop.
    //2. the other one is we take stack-top's right child as the next node to push into stack.
                    while (!stack.isEmpty() && cur == stack.peek().right) {//If the latest pop node is my right child, so i konw i am safe to pop now.
                        cur = stack.pop();res.add(cur.val);
                    if (stack.isEmpty()) break;
                    cur = stack.peek().right;
                } else //It has non-null right child, so the next Node to push is right child.
                    cur = top.right;
            return res;

Log in to reply

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