二叉树 后序遍历

Question

1、递归后序

static void postOrder(Node T) {
  if (T == null)
    return;
  postOrder(T.left);
  postOrder(T.right);
  System.out.print(T.val + " ");
}

2、非递归后序

1)、双栈法

这个其实就是非递归前序( iterativePre3 ) 的稍微一点改进。

• 首先，前序遍历入栈( iterativePre3 ) 的顺序是先 右　再左；
• 这时，我们可以做到反过来先　左　再右，这样遍历的顺序可以做到 "中右左"，而后续遍历是 "左右中"，正好是前面那个的相反，所以我们再使用一个栈反转保存即可；

/**
* 非递归后续 1(双栈法解决非递归后续)
* 后续遍历是要实现　　　左->右->中
* 这个方法和前序遍历的第二种方法　只是多了一个栈而已
* 因为　前序遍历是  中->左->右　　压栈顺序是 右->左
* 这样，我们就很容易实现　中->右->左遍历　　压栈顺序是　左->右
* 而后续遍历是要实现  左->右->中，
* 我们把上面的　　中右左　压入到另一个栈中　就实现了　左右中
*/
static void iterativePos(Node root) {
  Stack<Node> s = new Stack<>(), s2 = new Stack<>();
  Node p;
  s.push(root);
  while (!s.empty()) {
    p = s.pop();
    s2.push(p);
    if (p.left != null) s.push(p.left); //这里是先左再右  (非递归前序是先右再左)
    if (p.right != null) s.push(p.right);
  }
  while (!s2.empty())
    System.out.print(s2.pop().val + " ");
}

2)、设置 pre 结点

过程如下：

• 对于任一结点 p ，先将其入栈；
• 可以访问的情况: ①若 p 不存在左孩子和右孩子，则可以直接访问它。②或者 p 存在左孩子或者右孩子，但是左孩子和右孩子都已经被访问过了，则也可以直接访问该结点；
• 若非上述两种情况，则将右孩子和左孩子依次入栈。这样可以保证每次取栈顶元素时，左孩子在右孩子前面被访问，根结点在左孩子和右孩子访问之后被访问；

/*** 非递归后续 2(设置 pre 结点) */
static void iterativePos2(Node root) {
  Node cur, pre = null;
  Stack<Node> s = new Stack<>();
  s.push(root);
  while (!s.empty()) { 
    cur = s.peek();
    // 两种可以访问的情况
    if ((cur.left == null && cur.right == null) ||
      ((pre != null) && (pre == cur.left || pre == cur.right))) {
      System.out.print(cur.val + " ");
      s.pop();
      pre = cur;
    } else {
      if (cur.right != null) s.push(cur.right);
      if (cur.left != null) s.push(cur.left);
    }
  }
}