Iterative method (five lines of code)

The first order

thought

Keep walking until you reach the end of the left subtree, iterating through the values of the current node as you go, then turn to the right subtree of the parent node, and repeat the process

Reference code

In the sequence traversal

thought

It is similar to sequential traversal, but the value is accessed at the beginning after the end

Reference code

After the sequence traversal

thought

Because after traversal: left and right root (can be obtained by flipping ‘root right to left’, and ‘root right to left’ and the prior traversal ‘root left and right’ code can be fine tuned)

Reference code

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root; // The current node
        while(! stack.isEmpty() || cur ! =null) {while(cur ! =null) {Go straight to the right
                res.add(cur.val);
                stack.push(cur);
                cur = cur.right;
            }
            // When empty, i.e. the parent of the current node has no right child tree, go to the left child tree of the parent, and repeat
            TreeNode node = stack.pop();
            cur = node.left;
        }
        Collections.reverse(res);// Flip the list
        returnres; }}Copy the code