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


  • 0
    W

    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) {
                    stack.push(cur);
                    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();
                    res.add(cur.val);
    //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.