非递归后序遍历二叉树算法

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