方法1

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

看著代碼進(jìn)行分析。

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;
        }
    }
}

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

葉子節(jié)點判斷

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

右子樹是否遍歷完判斷

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

接下來還有一個問題，前序和中序遍歷時，在彈出一個節(jié)點時都是直接讓 p = p.right ，接著去訪問右子樹，后序遍歷有點不同。第一次彈出這個節(jié)點時，和前序和中序一樣，需要接著去訪問其右子樹，使 p = p.right ;但是當(dāng)?shù)诙螐棾鲞@個節(jié)點時，即上面判斷它的右子樹已經(jīng)訪問完了時，就不能再去訪問右子樹了，要不就會死循環(huán)了，應(yīng)該讓 p = null，繼續(xù)出棧元素。

懂了上面上面代碼后，發(fā)現(xiàn)其實上面兩個分支可以合成一個，所以最后的代碼如下。

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方法和前序中序一樣，只是它的遍歷點不一樣，它是在每個節(jié)點第二次訪問時將它的左樹的最右序列反著遍歷一遍。但是這樣會導(dǎo)致整個樹的最右序列沒有遍歷，所以最后還要加一個整個樹的最右序列遍歷。這應(yīng)該是最麻煩的二叉樹遍歷方法了。代碼如下。

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;
}