【原】Morris的后序遍历

在很久以前讲过Morris的前序遍历和中序遍历，488，二叉树的Morris中序和前序遍历。关于Morris的后序遍历没有讲，因为相对于前序和中序遍历，后序遍历稍微要复杂一些。关于前面讲的，如果没有左子节点，打印完当前节点之后直接跳到他的右子节点了，如果有左子节点，打印完当前节点和左子节点也跳到右子节点了，而后序遍历的顺序是：左子树->右子树->根节点，所以我们没法在打印完两个子节点之后在回来打印当前节点。

我们再来观察一下后序遍历的顺序，如下图所示，最先打印的是节点 4 ，这个是节点 2 的左子节点，接着打印的是节点 [5，2]，这个是节点 1 的左子节点往右走的逆序 …… ，所以我们发现如果当前节点没有左子节点不需要打印，如果有左子节点，直接打印左子节点一直往右走的逆序就行了。

通过前面 Morris 的前序和中序遍历我们知道，如果当前节点有左子节点，当前节点会被访问两次，那么这里是在第一次访问的时候打印还是在第二次访问的时候打印呢？通过下图我们可以发现是在第二次访问的时候打印。这里要注意因为节点 1 是根节点，他没有父节点，所以最右侧的不会被打印到，在最后的时候要单独打印。

对于后序遍历就是：

• 如果当前节点 cur 没有左子节点，不用管。

• 如果当前节点 cur 有左子节点，需要在第二次访问 cur 的时候打印"左子节点一直往右走的逆序"。

• 最后根节点往右的逆序要单独打印。

最后再来看下代码。

 public List<Integer> postorderTraversal(TreeNode root) {
     List<Integer> posList = new ArrayList<>();
     TreeNode cur = root;// 记录当前访问的节点。
     while (cur != null) {
         if (cur.left == null) {// 左子节点为空不用管。
             cur = cur.right;
        } else {
             TreeNode pre = cur.left;
             while (pre.right != null && pre.right != cur)
                 pre = pre.right;
             if (pre.right == null) {// 第一次到当前节点。
                 pre.right = cur;
                 cur = cur.left;
            } else {// 第二次到当前节点。
                 pre.right = null;
                 // 1，当前节点第二次访问的时候逆序打印。
                 printList(cur.left, posList);
                 cur = cur.right;
            }
        }
    }
     // 2，根节点往右的逆序要单独打印。
     printList(root, posList);
     return posList;
 }
 
 // 逆序打印
 private void printList(TreeNode node, List<Integer> posList) {
     // 这里并不是直接逆序打印，而是在打印的时候往前插入，
     // 比如要逆序打印1，2，3。首先打印 1 ，结果是[1]。
     // 在打印 2，打印的时候往前插入，结果是[2，1]
     // 接着打印 3，打印的时候往前插入，结果是[3，2，1]
     int size = posList.size();
     while (node != null) {// 这里面是插入。
         posList.add(size, node.val);
         node = node.right;
    }
 }