树结构

前序遍历

前序遍历的顺序是根节点 - 左子树 - 右子树，遍历的方式是:

1. 初始化栈，栈中只有根节点
2. 如果栈不为空，则出栈。访问出栈节点，并按右节点，左节点的方式添加到栈中(如果对应节点不为空)。
3. 重复步骤2，直到栈为空

用Python实现如下:

def preorder(root):
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        node.right and stack.append(node.right)
        node.left and stack.append(node.left)
    return res
# res: [1, 2, 4, 5, 3, 6, 7]
# 遍历的节点与其对应栈的状态如下(压栈后):
# 1 [3, 2]
# 2 [3, 5, 4]
# 4 [3, 5]
# 5 [3]
# 3 [7, 6]
# 6 [7]
# 7 []

中序遍历

前序遍历的顺序是** 左子树 - 根节点 -右子树**，遍历的方式是:

1. 初始化栈为空，节点指针为根节点
2. 当节点不为空时，将指针指向的节点放入栈，并将指针指向节点的左子树
3. 出栈并访问，并将指针指向右子树
4. 重复 2-3 直到节点与栈同时为空(即需要出栈时栈为空)
   用Python实现如下:

def inorder(root):
    stack = []
    node = root
    res = []
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            res.append(node.val)
            node = node.right
    return res
# res: [4, 2, 5, 1, 6, 3, 7]

后序遍历

后序遍历的顺序为右子树-左子树-根节点，遍历方式为:

1. 初始化栈中包含根节点
2. 出栈，访问出栈节点，并将节点左右节点添加到栈中
3. 重复2，直到栈为空
4. 逆序输出结果集

此方法远比网上的两个栈实现的方式精妙，来源于官方题解-二叉树后序遍历。用Python实现为：

def postorder(root):
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.insert(0, node.val) # 每次插入到最前端，相当于输出反向
        node.left and stack.append(node.left)
        node.right and stack.append(node.right)
    return res
# res: [4, 5, 2, 6, 7, 3, 1]

层次遍历

层次遍历顺序为按层进行遍历，遍历方式为:

1. 初始化队列中包含根节点
2. 出队列，访问出队列节点，并将节点左右节点添加到栈中
3. 重复2，直到队列为空

用Python实现为:

def layer_order(root):
    que = Queue()
    que.put(root)
    i = 0
    res = defaultdict(list) 
    while not que.empty(): # 层级循环
        new_que = Queue() # 用两个 queue 便于分辨节点处于哪一层
        while not que.empty(): # 层內元素循环
            node = que.get()
            res[i].append(node.val)
            node.left and new_que.put(node.left)
            node.right and new_que.put(node.right)
        que = new_que
        i += 1
    return dict(res)

遍历使用场景

• 前序遍历: