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]:
        res = []
        self.travel(root, res)
        return res

    def travel(self, root, res):  #辅助函数，注意要将结果集作为参数传入，才能在递归中修改结果集
        if root:            
            self.travel(root.left, res)                   
            self.travel(root.right, res)
            res.append(root.val)

解法二：用栈。

左右中的顺序，关键是判断左右是否已访问，且是先左后右，才能访问中。用cur表示当前访问，last表示上一次访问。

初始将根放入栈，last初始为根

每次令cur为当前栈顶，但是不弹栈

1）若cur左子非空，且cur左子和右子都不为last，则cur的左子入栈。解释：last是最近弹栈并输出的节点，若last等于cur的左子或右子，说明cur的左子树和右子树都已输出，此时不应将cur的左子入栈。否则说明左子树还没处理，将cur的左子入栈

2）若1不成立，且cur的右子非空，last不为cur的右子，则cur的右子入栈。解释：若last为cur的右子，说明cur的右子已输出，此时不应再将cur的右子入栈，否则说明右子树还没处理，要将cur的右子入栈

3）若1和2都不成立，说明cur的左子和右子都已输出，则将cur弹栈，并将cur标记为last

class Solution:
    def postorderTraversal(self, root: TreeNode) :
        res = []
        last = root  #记录上一个访问节点，初始为根
        if not root:
            return res
        s = [root]
        while s:
            # 取栈顶作为本轮的根节点，注意最后才访问所以不能出栈
            cur = s[-1]
            # 1. c的左子非空，且左子和右子都没处理过
            if cur.left and cur.left != last and cur.right != last:
                s.append(cur.left)
            # 2. 若1不成立，且c的右子非空，且右子未处理过
            elif cur.right and cur.right != last:
                s.append(cur.right)
            # 3. 若1和2不成立，说明c的左子树和右子树都已处理，将cur弹栈并输出，last标记为cur
            else:
                cur = s.pop()
                res.append(cur.val)
                last = cur
        return res