二叉树的前中后序遍历到底是什么？
1. 前言吐槽
刷过 Leetcode 的牛马都知道二叉树是逃不过去的坎儿，尤其是遍历，修改等等。遍历又分成层序遍历，前序中序后序遍历，然后实现方法又分成迭代和递归，每次去敲代码都因为一些细节卡死，比如什么时候打印，什么时候修改，好不容易代码通过了，隔了一段时间，好家伙又忘记怎么写的了
本质上还是对于二叉树理解不够透彻，就比如很长一段时间后，很可能根本不记得前中后序的遍历规则是什么了。这篇文章就是基于刷过的各种文章来做个小结，以便未来忘记了再来快速回忆一下（希望不要再回忆了。。。）
2. “序”到底是什么
序 顾名思义就是顺序。而要有顺序，就得有参考坐标。一般来说，我们会把二叉树的根节点作为参考坐标，类似的每次递归子二叉树的时候，对应二叉树的根节点也就是当前递归轮次的参考坐标了。
参考坐标很好理解，那为什么分成前中后序呢？为什么不是先后（左右）序呢？
“中”序的中又是指什么呢？这些概念最近刷到文献[1]后才豁然开朗。
我们以下面二叉树的节点 2 为例。可以看到遍历节点 2 通常会有 3 次：
- 第一次是从根节点 1 到节点 2
- 第二次是节点 2 到节点 3，然后节点 3 返回到节点 2
- 第三次是节点 4 返回 到节点 2
对于每个节点都是会经过 3 次，即使是节点 7 也是如此，即使它的左右节点都是空，但是也可以看作从 左右空节点返回节点 7。
至此，其实就是前中后序的由来（或者一种方便理解的解释）。第一次进过节点就是该节点的前序，第二次就是中序，第三次就是后序。
一个比较有意思的说法：所以对于任意一个节点而言，后序包含的信息量是最大的，还是以节点 2 为例，它的前序只有节点 1 的信息，中序增加了节点 3 （及其子节点）的信息，后序增加了节点 4（及其子节点）的信息。
3. 递归遍历
了解了前中后序的含义后，那我们自然也就是到为什么前序遍历打印的结果是（根节点，左节点，右节点）了，因为打印操作是在第一次进入该节点执行的，对应到代码就是：
def traverse(root):
if not root:
return None
# 第一次进入该节点
print(root.val)
traverse(root.left)
traverse(root.right)
那中序呢？很简单，就是在第二次进入节点的时候执行的操作
def traverse(root):
if not root:
return None
# 第一次进入该节点
traverse(root.left)
# 第二次进入该节点
print(root.val)
traverse(root.right)
后序同理
def traverse(root):
if not root:
return None
# 第一次进入该节点
traverse(root.left)
# 第二次进入该节点
traverse(root.right)
# 第三次进入该节点
print(root.val)
你可能会说这很简单啊，只要记住前中后序的对应递归代码就好了呀。但是对我而言，上面的逻辑能够帮助我跳脱出递归的代码逻辑，从一个更高的维度来写代码，逻辑会更加清晰，有一种呼吸道新鲜空气的感觉，而不是陷在递归的逻辑沼泽里难以呼吸（有同感的吗 hh）
4. 迭代遍历
除了递归遍历，另一种遍历方法是迭代遍历，就和 for 循环一样显式的写出来遍历过程，这种遍历方式更好理解，在求解二叉树的深度的时候会有奇效
from collections import deque
def iterative(root):
Q = deque(root)
depth = 0
while Q:
num = len(Q) # 当前层的队列长度
for i in range(num):
node = Q.popleft()
if Q:
# 下面两行会把左右节点都插入到队列，但有可能是空节点
# 所以为了下一轮遍历，需要判断试一下是否为空节点
Q.append(node.left)
Q.append(node.right)
depth += 1
return depth
迭代遍历通常会用到 deque (double-ended queue 双端队列)，为了实现层序遍历，那逻辑很简单，就是先把第 i 层（从 0 开始）的所有节点插入到队列里，并记下数量 $n_i$，然后遍历这些数量的节点。 遍历第 i 层节点的同时继续把这些节点的左右节点插入到队列了，遍历完了就是就等价于把第$i+1$层节点也都插入到队列里了，类似地也记录下这一层的节点数量，重复迭代就实现了层序遍历。
有个特别注意的点：Q.append(node)是往队列右侧增加新的节点，为了保证顺序一致，我们需要用node = Q.popleft()来从左边取节点，如果用node = Q.pop()就是从右边取节点，这样就会出现逻辑错误
至此，你了解了二叉树的递归遍历，迭代遍历，前中后序遍历。接下来我们可以继续尝试用迭代遍历实现前中后序遍历：
- 前序
# 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
from collections import deque
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
Q = deque([root])
vals = []
while Q:
node = Q.popleft()
if node:
vals.append(node.val)
Q.appendleft(node.right)
Q.appendleft(node.left)
return vals
- 中序
# 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
from collections import deque
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
Q = deque([])
node = root
vals = []
while Q or node:
while node:
# while node and not hasattr(node, 'viist'):
# node.visit = True
Q.append(node)
node = node.left
node = Q.pop()
vals.append(node.val)
node = node.right
return vals
- 后序
# 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
from collections import deque
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
vals = []
Q = deque([])
node = root
while Q or node:
while node:
Q.append(node)
if node.left:
node = node.left
else:
node = node.right
node = Q.pop()
vals.append(node.val)
if Q and Q[-1].left == node:
node = Q[-1].right
else:
node = None
return vals