二叉树的前序遍历、中序遍历、后序遍历、层次遍历

写在前面：

实现语言：Python3

二叉树是数据结构里面非常重要的结构:

DFS（深度优先遍历）有前序遍历、中序遍历、后序遍历

BFS（宽度优先便利）有层序遍历

重点：

DFS的实现实际利用的结构是 stack（先进后出）

BFS利用的结构是queue（先进先出）

思考：我们经常关注迭代与递归的关系，其实说白了迭代就是模拟递归，建议阅读此文，写得非常好

URL：https://zhuanlan.zhihu.com/p/30490183

代码展示：

#Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

前序遍历（preorderTraversal）

# 迭代写法
class Solution:
    """前序遍历"""
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        stack = [(root,False)]
        res = []
        while stack:
            cur, vis = stack.pop()
            if vis:
                res.append(cur.val)
            else:
                if cur.right:
                    stack.append((cur.right, False))
                if cur.left:
                    stack.append((cur.left, False))
                stack.append((cur, True))               # 前序遍历
        return res

# 递归写法
#class Solution:
#    def preorderTraversal(self, root: TreeNode) -> List[int]:
#       if not root:return []
#       return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right) if root else []

中序遍历（inorderTraversal）

# 迭代写法
class Solution:
    """中序遍历"""
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        stack = [(root,False)]
        res = []
        while stack:
            cur, vis = stack.pop()
            if vis:
                res.append(cur.val)
            else:
                if cur.right:
                    stack.append((cur.right, False))
                stack.append((cur, True))             # 中序遍历
                if cur.left:
                    stack.append((cur.left, False))
        return res

# 递归写法
#class Solution:
#    def inorderTraversal(self, root: TreeNode) -> List[int]:
#        if not root:return []
#        return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right) if root else []

后序遍历（postorderTraversal）

# 迭代写法
class Solution:
    """后序遍历"""
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        stack = [(root,False)]
        res = []
        while stack:
            cur, vis = stack.pop()
            if vis:
                res.append(cur.val)
            else:
                stack.append((cur, True))     # 后序遍历
                if cur.right:
                    stack.append((cur.right, False))
                if cur.left:
                    stack.append((cur.left, False))
        return res

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

总结：不难发现前中后序只是调换了一行代码的位置而已 stack里面有两个参数，可以看成主角和配角，配角的作用是指出遍历到的元素是直接打印值还是丢进栈里面不管

层序遍历（levelOrder）

class Solution:
    """层序遍历"""
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res = []
        queue = [root]   # 用队列实现
        while queue:
            tmp = []
            for i in range(len(queue)):
                cur = queue.pop(0)
                tmp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(tmp)
        return res