LeetCode-145-二叉树的后序遍历

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

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

image.png

** 解题思路：**

1. 递归：略
2. 迭代方法：用栈stack来存储节点，向左一直遍历，直到不存在左节点，此时判断是否存在右节点和是否已经遍历过右节点；
3. 若存在右节点，则将当前节点入栈，并前进到右节点；
4. 若不存在右节点or已经遍历过右节点，当前节点的val存入res，pre指向当前节点，表示已访问过的节点，用于下次判断是否遍历过右节点；

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 递归
        if not root: return None
        res = []
        if root.left:
            res += self.postorderTraversal(root.left)
        if root.right:
            res += self.postorderTraversal(root.right)
        res += [root.val]
        return res

# 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]:
        # 左-右-根
        # 迭代
        stack = []
        node = root
        pre = None
        res = []
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            if not node.right or pre == node.right:  # 右节点不存在or已经遍历过右节点
                res.append(node.val)
                pre = node
                node = None
            else:  # 存在右节点，先保存当前节点，再遍历右节点
                stack.append(node)
                node = node.right
        return res