[数据结构与算法]145. 二叉树的后序遍历（迭代遍历）

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

对于后序遍历，由于遍历的顺序是左->右->中，所以某个节点在其左子树遍历完成后并不能立即出栈，而是要等待其右子树叶遍历完成后再出栈，那么我们如何知道当前这次出栈是因为左子树遍历完了还是右子树遍历完了呢？

所以我们要借助一种新的数据结构来辅助记录该节点是第一次出栈还是第二次。如下

 class TagNode{
      TreeNode node;
      boolean flag;

      public TagNode(){}
      public TagNode(TreeNode node ,boolean flag){
         this.node = node;
         this.flag = flag;
      }
  }

可以看到TagNode包含两个字段，一个是树的节点，一个是标志字段flag，刚开始flag字段初始化为false，

如果因为当前节点的左子树遍历完成而导致当前节点出栈时，我们将这个flag字段的值更新为true，然后再将其压入栈中，然后等到其右子树遍历完成后，该节点出栈时，检查标志位flag的值为true，才可以真正的出栈。

举例说明二叉树的后序遍历的遍历过程。

为1节点新创建一个TagNode，flag为false，并入栈

随后指针移动到1节点的子节点，发现为null。

栈顶元素出栈，检查flag标志为发现为false，表示这是第一次出栈，我们将flag的值改为true再将这个节点压回栈中，转而遍历其右子树。

然后为2节点创建一个TagNode flag设置为false，压入栈中

递归遍历左子树，直至为null

此时now指针为null，栈顶元素出栈，检查flag值为false，将flag值变为true后再次压入栈中，转而遍历其右子树。

然后发现，其右子节点的值同样是null，该节点再次出栈，检查其flag值为true，符合出栈要求，将其值加入res数组后将其出栈。

此时，now依然指向null，所以我们仍然需要从栈中出栈一个元素，所以由将2节点出栈，检查其flag值为flase,将flag值变为true后再次压入栈中,转而遍历其右子树。

但不幸的是，此时2节点的右子树依然为null，所以我们再次将栈顶节点 2节点出栈，检查其flag值为true，符合出栈要求，将其值加入res数组后，出栈该节点。

此时，now指针依然指向null，所以需要从栈中再次出栈一个节点，这个节点是1节点，检查其flag值为true，符合出栈要求，将其值加入res数组后，将该节点出栈。

此时，now指向null且栈中无任何可出栈元素，遍历过程结束，得到所求的数组res。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  static class TagNode{
      TreeNode node;
      boolean flag;

      public TagNode(){}
      public TagNode(TreeNode node ,boolean flag){
         this.node = node;
         this.flag = flag;
      }
  }
  public List<Integer> postorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      if(root == null){return res;}

      Deque<TagNode> stack = new ArrayDeque<>();
      TreeNode now = root;
      TagNode node ;
      while(now != null || !stack.isEmpty()){
        while(now != null){
          node = new TagNode(now,false);
          stack.push(node);
          now = now.left;
        }

        node = stack.pop();
        if(node.flag == true){
          res.add(node.node.val);
        }else{
          node.flag = true;
          stack.push(node);
          now = node.node.right;
        }
      }
      return res;
    }
}

总结：

• 进易出难：对于某个节点，只要now指针指向它就立刻将其入栈，而如果想将一个节点出栈，那么必须要两次检查flag值，满足条件才可以出栈。
• 如果出栈节点的flag节点值为false，说明其右子树还未被遍历，更新flag值后重新压入栈中，now指针转而指向其右子树
• 如果出栈节点的flag节点值为true,说明其左右子树均已被遍历，满足出栈条件。
• 内部类要用static表示为静态类。