题目：二叉树的后序遍历

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

示例:

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

进阶:递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）第145题

链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

分析：

方法有很多，递归法最简单，迭代法使用栈辅助完成，还有莫里斯遍历。本文讲解官方写的题解迭代法。虽然我也写出了迭代法，但是官方的解法既简单又高效，非常厉害。使用了迭代法+逆向工作法。

思路：

• 后序遍历是左，右，中。可是中在最后，如果正常解后序遍历的话有的复杂。
• 如果我们用中，右，左这样来遍历的话岂不是将后序遍历变成了前序遍历的翻版类型。
• 这样的话答案只是与我们要求的答案相反，翻转一下列表就可以了。
• 所以解法就是一个反向的先序遍历方法。

代码：

• 官方的迭代法+逆向工作法

  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution:
  def postorderTraversal(self, root: TreeNode) -> List[int]:
      if root is None:
          return []
      stack = [root]
      res = []
      while stack:
          root = stack.pop()
          res.append(root.val)
          if root.left is not None:  # 先加左再加右，出栈的时候就是先加右，再加左。
              stack.append(root.left)
          if root.right is not None:
              stack.append(root.right)
      return res[::-1]
  

• 我自己写的迭代法，内容有点复杂，不是很好理解。

  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
  def postorderTraversal(self, root):
      stack = []
      helper = []
      res = []
      while stack or root:
          while root:
              stack.append(root)
              root = root.left
          helper.append(stack[-1])
          root = stack.pop().right
          if root is None:
              res.append(helper.pop().val)
              while stack and stack[-1].left in helper and helper:
                  res.append(helper.pop().val)
              while not stack and helper:
                  res.append(helper.pop().val)
      return res
  

• 虽然我的方法写的多了一点，但是速度和官方的一样，甚至有时比官方解法快。

复杂度分析：

• 两种方法相同，都是迭代法：
  • 时间复杂度：O(n) n为树的所有节点。
  • 空间复杂度：O(n)

总结：

• 再一次遇到逆向工作法，事实证明如果你遇到问题解不开来反向解一下，思路清晰，易于求解。