方法1

非遞歸用棧來輔助遍歷，后序遍歷是第三次遇到該節點再遍歷，但是棧只能給我們提供遇到兩次的判斷方法，第一次是入棧時，第二次是出棧時，它們分別對應著二叉樹的先序和中序遍歷。所以我們需要利用一些技巧來輔助我們判斷，這也是后序遍歷二叉樹比先序和中序稍微復雜一點的原因。

看著代碼進行分析。

public static void postOrderTraverse(TreeNode root) {
    TreeNode p = root;
    TreeNode pre = null;
    LinkedList<TreeNode> stack = new LinkedList<>();
    while (p != null || stack.size() != 0) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        if (p.right == null) { // leaf 
            pre = p;
            System.out.println(p.val);
            p = p.right;
        } else if (p.right == pre) { // pre is p.right
            pre = p;
            System.out.println(p.val);
            p = null;
        } else {  // p.right dont traverse
            stack.push(p);
            p = p.right;
        }
    }
}

過程和前序中序基本一樣，那什么時候我們需要遍歷呢?當這個節點是葉子節點時或當這個節點的右子樹已經遍歷完了時就可以遍歷了，否則我們再次將它入棧，等待下次遍歷。同時也說明只有當這個節點是葉子節點或者這個節點的右子樹已經訪問完了時這個節點才能順利出棧。

葉子節點判斷

葉子節點很好判斷，只要它的右孩子為 null 就代表它是葉子節點，因為左孩子一定為 null，否則不會從前面那個 while 中跳出。

右子樹是否遍歷完判斷

看上面代碼，我們是在順利出棧的時候進行遍歷，而后序遍歷當前節點的上一個遍歷節點就是它的右孩子，我們用 pre 記錄上次順利出棧的節點，判斷如果當前節點的右子節點就是上一個順利出棧的節點，代表右子樹已經遍歷完了，就遍歷當前節點。

接下來還有一個問題，前序和中序遍歷時，在彈出一個節點時都是直接讓 p = p.right ，接著去訪問右子樹，后序遍歷有點不同。第一次彈出這個節點時，和前序和中序一樣，需要接著去訪問其右子樹，使 p = p.right ;但是當第二次彈出這個節點時，即上面判斷它的右子樹已經訪問完了時，就不能再去訪問右子樹了，要不就會死循環了，應該讓 p = null，繼續出棧元素。

懂了上面上面代碼后，發現其實上面兩個分支可以合成一個，所以最后的代碼如下。

public static void postOrderTraverse(TreeNode root) {        
    TreeNode p = root;
    TreeNode pre = null;
    LinkedList<TreeNode> stack = new LinkedList<>();
    while (p != null || stack.size() != 0) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        // left or pre is p.right
        if (p.right == null || p.right == pre) { 
            pre = p;
            System.out.println(p.val);
            p = null;
        } else {  // p.right dont traverse
            stack.push(p);
            p = p.right;
        }
    }
}

方法2 Morris方法

Morris方法和前序中序一樣，只是它的遍歷點不一樣，它是在每個節點第二次訪問時將它的左樹的最右序列反著遍歷一遍。但是這樣會導致整個樹的最右序列沒有遍歷，所以最后還要加一個整個樹的最右序列遍歷。這應該是最麻煩的二叉樹遍歷方法了。代碼如下。

public static void postOrderTraverse(TreeNode root) {
    TreeNode cur = root;
    TreeNode rightmost = null;
    while (cur != null) {
        if (cur.left != null) {
            rightmost = cur.left;
            while (rightmost.right != null && rightmost.right != cur) {
                rightmost = rightmost.right;
            }
            if (rightmost.right == null) {
                rightmost.right = cur;
                cur = cur.left;
            } else {
                rightmost.right = null;
                reverseTraverse(cur.left);
                cur = cur.right;
            }
        } else {
            cur = cur.right;
        }
    }
    reverseTraverse(root);
}
public static void reverseTraverse(TreeNode node) {
    TreeNode head = reverse(node);
    TreeNode p = head;
    while (p != null) {
        System.out.println(p.val);
        p = p.right;
    }
    reverse(head);
}
public static TreeNode reverse(TreeNode node) {
    if (node == null || node.right == null) {
        return node;
    }
    TreeNode cur = node;
    TreeNode next = node.right;
    TreeNode temp = node.right;
    cur.right = null;
    while (next != null) {
        temp = next.right;
        next.right = cur;
        cur = next;
        next = temp;
    }
    return cur;
}