145. Binary Tree Postorder Trave

首先是递归的写法

# 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]:
        if not root:
            return []
        
        result = []
        result += (self.postorderTraversal(root.left))
        result += (self.postorderTraversal(root.right))
        result.append(root.val)
        return result
        

解法二:
用根节点初始化栈，然后使用一个pre节点记录上一次访问的节点。
当栈不空的时候不断循环。
若当前栈顶节点的左右子节点均为空或者当前节点的左或右子节点是上一次访问过的节点，则说明当前节点此时可以被访问了。
否则，依次将右左节点入栈。

# 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]:
        if root is None:
            return []
        result = []
        pre = root  #指向上一次访问的节点
        stack = [root,]
        while len(stack):
            cur = stack[-1]
            if (not cur.left and not cur.right) or cur.left == pre or cur.right == pre:
                result.append(cur.val)
                # print('result',result)
                stack.pop()
                pre = cur
            else:
                if cur.right:
                    stack.append(cur.right)
                if cur.left:
                    stack.append(cur.left)
        return result