方法1

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

看著代碼進(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;
        }
    }
}

過(guò)程和前序中序基本一樣，那什么時(shí)候我們需要遍歷呢?當(dāng)這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)時(shí)或當(dāng)這個(gè)節(jié)點(diǎn)的右子樹(shù)已經(jīng)遍歷完了時(shí)就可以遍歷了，否則我們?cè)俅螌⑺霔＃却麓伪闅v。同時(shí)也說(shuō)明只有當(dāng)這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者這個(gè)節(jié)點(diǎn)的右子樹(shù)已經(jīng)訪問(wèn)完了時(shí)這個(gè)節(jié)點(diǎn)才能順利出棧。

葉子節(jié)點(diǎn)判斷

葉子節(jié)點(diǎn)很好判斷，只要它的右孩子為 null 就代表它是葉子節(jié)點(diǎn)，因?yàn)樽蠛⒆右欢?null，否則不會(huì)從前面那個(gè) while 中跳出。

右子樹(shù)是否遍歷完判斷

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

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

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

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

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