二叉树共有两类遍历方式（理解前中后序+层序）
DFS：深度优先搜索：即前中后三序遍历
所谓前中后序就是：
“左”，“中”，“右”这三个元素组成的排列中“中”的位置，
中代表处理节点，
左代表访问左孩子
右代表访问右孩子
前序遍历：中左右，先处理节点后访问左右孩子
中序遍历：左中右，先访问左孩子，再处理节点，后访问右孩子
后序遍历：左右中，先访问左右孩子，后处理节点
PS：
一颗二叉树有唯一的三序遍历与其对应，
但某一个三序遍历序列并不一定存在唯一一颗二叉树与之对应，
有点像一向箔把一个二维实体一维话的感觉，
三序遍历产生的序列其实可以看做一个个的区域组成，
每个区域（特定子序列）都有原二叉树的某个子树与之对应，
但问题就是你找不到各个区域的分界点在哪，
所以只能单向映射
BFS：广度优先搜索：
层序遍历：一般由队列实现
个人感觉二叉树的遍历是二叉树中最重要的部分
最好能练到肌肉记忆的程度
一、二叉树的深度优先遍历
1.递归
模板都一样，
区别仅在于访问左孩子、访问右孩子和处理节点的顺序：
前序：
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(root):
if not root:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return ans中序：
# 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 inorder(self, root, res):
if not root:
return
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.inorder(root, res)
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: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
ans.append(root.val)
dfs(root)
return ans当然也可以写成先判断左右孩子是否存在再访问的形式
2.迭代
2.1 前序法
（代码随想录 二叉树-3中的前序遍历（迭代法）和后续遍历（迭代法））
代码逻辑很简单：就是访问到哪里处理到哪里
我把它叫做前序法原因除了逻辑上是前序外，
还有这个方法基本上只能用在前序遍历上
只有组数组的过程才可能会用到前序遍历
这个方法优点是除递归外实现前序遍历最简单的方法，
缺点是绝不访问同一个节点两次
所以不支持中序遍历，
且除非保存访问结果（大部分情况），否则也不支持后续遍历
实现前序遍历：
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans实现后续遍历：
# 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: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans[::-1]2.2 指针法
（代码随想录 二叉树-3中的中序遍历（迭代法））
由于中序遍历的实现需要先找到二叉树最左端的节点，
再进行访问，
这个向某个方向探底的逻辑，
非常适合用指针来实现，
所以中序遍历的迭代法可以用指针来实现：
代码逻辑就是先向左探到底并记录路径，
到底之后沿着路径往回走一步，再往右走一步，
然后继续向左探底，直到访问过所有节点：
实现中序遍历：
# 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: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans, stack = [], []
cur, prev = root, None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if not cur.right or cur.right == prev:
ans.append(cur.val)
prev = cur
cur = None
else:
stack.append(cur)
cur = cur.right
return ans然而，这种逻辑真的只能用于实现中序遍历吗？
显然不是的，
事实上这种逻辑不仅能实现中序遍历，
不要忘了，需要第二次访问一个节点的序列还有后续遍历，
但和实现中序遍历不同的是，
实现后续遍历需要访问左右孩子后再访问父节点，
所以需要第二个节点来记录
实现后序遍历：
# 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: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans, stack = [], []
cur, prev = root, None
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if not cur.right or cur.right == prev:
ans.append(cur.val)
prev = cur
cur = None
else:
stack.append(cur)
cur = cur.right
return ans当然了，前序遍历也可以用指针法实现，
只是没有必要，
但写一写感觉对于理解指针法中的每一行代码是在做什么是有帮助的，
实现前序遍历：
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans, stack = [], []
node = root
while node or stack:
if node:
ans.append(node.val)
stack.append(node)
node = node.left
else:
node = stack.pop()
node = node.right
return ans此外，
指针法的向左探底的逻辑有两种写法：
一种是用if，比较好理解，本文的前序和后序用的是if写法
另一种是用while，本文的中序用的就是while写法
2.3 统一迭代法
（代码随想录二叉树-4）
统一迭代法的代码逻辑是每个节点都访问两次，
每次分别做的不一样的事情：
第一次，反序打标记：
每当第一次访问到一个节点，
就把当前节点极其左右孩子按照对于顺序（前后中）的反序压入栈中
第二次，处理节点：
每当遇到打好标记的节点，
便处理节点
这样利用栈的反序特性，
第二次访问的时候也就是处理节点的顺序就是对应顺序的遍历了
打标记的方法有两种：
空写法：一种是将当前节点压入栈后立即压入一个空节点，
让空节点充当标记
元组写法：另一种是使用多个栈或元组（python）的方式用true和false打标签，
未访问标false，
访问过的标true:
实现前序遍历（空写法）：
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
if node:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
stack.append(node)
stack.append(None)
else:
node = stack.pop()
ans.append(node.val)
return ans实现中序遍历（元组写法）：
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: # 左中右
return []
ans = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if not visited:
if node.right:
stack.append((node.right, False)) # 右
stack.append((node, True)) # 中
if node.left:
stack.append((node.left, False)) # 左
else:
ans.append(node.val)
return ans实现后序遍历（空写法）：
# 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: Optional[TreeNode]) -> List[int]:
if not root: # 左右中
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
if node:
stack.append(node) # 中
stack.append(None)
if node.right:
stack.append(node.right) # 右
if node.left:
stack.append(node.left) # 左
else:
node = stack.pop()
ans.append(node.val)
return ans二、二叉树的广度优先遍历（层序遍历）
层序遍历的关键逻辑在于：
每访问一层求一次长度，
然后层内for循环访问节点，
代码实现：
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans = []
que = collections.deque()
que.append(root)
while que:
n, cur = len(que), []
for i in range(n):
node = que.popleft()
cur.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
ans.append(cur)
return ans附录：安装方式（如果手生了或忘了）
简易安装：
三序递归（简单）+ 前序遍历：前序法迭代（简单） + 三序统一迭代法（一法三用）+ 层序遍历
完全安装：
1.三序递归+
2.三序统一迭代法
3.层序遍历
4.其他三序迭代法
前序遍历：前序法 + 指针法
中序遍历：指针法
后序遍历：前序法 + 指针法
标签：node,遍历,val,self,right,二叉树,left,root,刷题 From： https://blog.csdn.net/weixin_44610684/article/details/144970870