二叉树的遍历-----递归和迭代模板总结~超简单。

先序: 左右根
中序: 左根右
后序: 左右根

先说递归：

先序:

def preTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            res.append(root.val) # 访问根节点
            dfs(root.left)    # 递归左
            dfs(root.right)    # 递归右
    dfs(root)
    return

中序:

def inorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
    dfs(root)
    return

后序:

def laterTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
    dfs(root)
    return

迭代:

先序:

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        res, stack = [], []
        while root or stack: # stack为空且node为null时，说明遍历结束
            while root: # 可以进入左子树时，先访问，再进入
                res.append(root.val)
                stack.append(root)
                root = root.left
            root = stack.pop()
            root = root.right # 否则进入栈中节点的右子树
        return

中序:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:

        if not root: return []  # 若root为空则直接返回空
        res, stack = [], []
        while root or stack: # stack为空且root为null时，说明已经遍历结束
            while root: # 可以深入左子树
                stack.append(root)
                root = root.left
            root = stack.pop() # 否则访问栈中节点，并深入右子树
            res.append(root.val)
            root = root.right
        return

后序:

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res, stack = [], []
        prev = None
        # prev记录刚刚访问的节点，
        # 如果当前访问节点是上次访问节点的父节点，则说明子树访问完成，可以访问当前节点了。
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 比前序和中序的模板增加一个判断过程：节点没有右孩子或已经访问了该节点的子节点
            if not root.right or root.right == prev:
                res.append(root.val)
                prev = root
                root = None     # 这里root必须要重新设置成None
                                # 因为走到这一步的时候，左右都已经是空的了。
                                # 预防再次循环的时候root进入到一开始的那个while
            else: # 存在右孩子没遍历
                stack.append(root)
                root = root.right
        return

后序稍微加了一个判断模块。画个树，手动模拟一下就理解了。
注释都写在代码里了，看一下就懂了~

另外两中方法的时间复杂度.

递归的

迭代的