145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

Python 解答：
1.递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def postOrder(root):
            if not root:
                return
            else:
                postOrder(root.left)
                postOrder(root.right)
                res.append(root.val)
        postOrder(root)
        return res

2.非递归,按根右左遍历再逆转

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        q = root
        while q or stack:
            if q:
                res.append(q.val)
                stack.append(q)
                q = q.right
            else:
                temp = stack.pop()
                if temp.left:
                    q = temp.left
        return res[::-1]

2.记录已访问节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        q = root
        visited = None
        while q or stack:
            while q:
                stack.append(q)
                q = q.left
            q = stack[-1]
            if not q.right or q.right == visited:
                res.append(q.val)
                stack.pop()
                visited = q
                q = None
            else:
                q = q.right
        return res