二叉树的遍历

二叉树的遍历是二叉树中的最基本操作，分成先序遍历、中序遍历、后序遍历，以及层次遍历。

二叉树的遍历，指的是按照一定的顺序逐个访问二叉树的节点。可以采用递归和非递归的形式进行，都很重要

先序遍历、中序遍历、后序遍历的区别在于什么时候访问父节点。

先序遍历：头节点-左节点-右节点 中序遍历：左节点-头节点-右节点 后序遍历：左节点-右节点-头节点

宽度优先遍历

宽度优先遍历指的就是层次遍历

深度优先遍历

即二叉树的先序遍历

递归访问二叉树

重要的先验知识

二叉树的遍历最简单的方法就是递归的写法

def f(head: Node):
	if head == None:
		return
	f(head.left)
	f(head.right)

上述代码是最朴素的，就对每个节点看一眼，但是没有任何操作，记住这个代码。

实际上，上述代码里，对于当前节点head，会”访问”3次，用 -> x 表示第x次进入，x->表示第几次出去。

def f(head: Node):
	# -> 1
	if head == None:
		return
	# 1 ->
	f(head.left)
	# -> 2
	# 2 ->
	f(head.right)
	# -> 3
	# 3 ->

从上代码中可以看出，除了第一次访问的时候会有操作（判断递归的终止条件），第2、3次的访问都没有任何操作就直接出去了。

接下来，假设有一个树

根据上述代码，我们写出该递归程序访问上图树种所有节点的顺序为（同一个节点被多次访问就多次记录）：

1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1

上述顺序（即按照上述代码访问节点的顺序），我们称之为递归序。我们在递归序的基础上完成对于前序、中序、后序的加工。

先序遍历

节点访问顺序：头节点-左节点-右节点

在递归序的基础上，我们第一次来到某个节点的时候打印该节点，第二三次访问时无操作

即代码为

def f(head: Node):
	# -> 1
	if head == None:
		return
	print(head.val)  # 第一次访问期间执行打印操作
	# 1 ->
	f(head.left)
	# -> 2
	# 2 ->
	f(head.right)
	# -> 3
	# 3 ->

中序遍历

节点访问顺序：左节点-头节点-右节点

在递归序的基础上，我们第二次来到某个节点的时候打印该节点，第一三次访问时无操作

def f(head: Node):
	# -> 1
	if head == None:
		return
	# 1 ->
	f(head.left)
	# -> 2
	print(head.val)  # 第二次访问期间执行打印操作
	# 2 ->
	f(head.right)
	# -> 3
	# 3 ->

后序遍历

节点访问顺序：左节点-右节点-头节点

在递归序的基础上，我们第三次来到某个节点的时候打印该节点，第一二次访问时无操作

def f(head: Node):
	# -> 1
	if head == None:
		return
	# 1 ->
	f(head.left)
	# -> 2
	# 2 ->
	f(head.right)
	# -> 3
	print(head.val)  # 第三次访问期间执行打印操作
	# 3 ->

层次遍历

节点访问顺序：从上到下逐层访问二叉树，在每层中从左到右依次打印节点。

解法三

思路：递归实现，对于层次遍历的递归实现，是需要使用一个指示变量来指示当前的层数，指示变量为几就指示当前的树在第几层，故可以通过下标直接访问res

题解：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def recur(cur, indLevel):
            # 递归退出条件
            if cur == None:
                return
            # 判断当前层是不是来过了，没来过要创建*当前层*的节点列表
            if len(res)-1<indLevel: # indLevel是从0开始的
                res.append([])
            
            recur(cur.left, indLevel+1)
            #中序操作，向结果中添加当前节点
            res[indLevel].append(cur.val) 
            recur(cur.right, indLevel+1)
        
        res = []
        recur(root, 0)
        return res

指向原始笔记的链接

非递归遍历二叉树

把递归变成非递归，需要用到栈。利用人工压栈的方式来替代系统给你压栈的行为。

同样还是这棵树

先序遍历_

创建一个栈，首先把根节点放进去，然后每次：

1. 从栈中弹出一个节点 cur
2. 打印（处理）该节点 cur
3. 把 cur 的右孩子压到栈里去，再把 cur 的左孩子压到栈里去
4. 重复 1-3 步

建议画图体会一下

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        stack.append(root)
        output = []
        while(len(stack)>0):
            cur = stack.pop()
            output.append(cur.val)
            if cur.right: stack.append(cur.right)
            if cur.left: stack.append(cur.left)
        return output

中序遍历_（较难）

创建一个栈，每次：

1. 当前子树的左边界从上到下依次进站
2. 弹出一个节点 cur
3. 对 cur 的右节点重复 1-3 步

你可以看看这个例子

什么是左边界？

一个树，沿着左孩走到没有左孩，这条路径就是左边界。

比如： 上图中的树的左边界为：1 2 4，以节点3为根节点的子树的左边界为 3 6

上图中的树的左边界为 1 2 4，以节点5为根节点的子树的左边界为 5 6 7，以节点3为根节点的子树的左边界为3 8，依次类推。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        self.addLeftBound(stack, root)
        while(len(stack)>0):
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack = self.addLeftBound(stack, cur.right)
        return res
            
    def addLeftBound(self, stack, node):
        while(node):
            stack.append(node)
            node = node.left
        return stack

为什么这么操作就是中序了呢？

因为所有的树都是可以被左边界分解掉的，如下图。 （同理也可以被右边界分解掉） 把左边界放到了栈里去是先头再左，那么弹出的时候就是先左再头。只不过右树是后做的。 换句话说，就是把二叉树按照左边界分解了，只不过右树后做，即

后序遍历_

后序的顺序是【左、右、头】，这就相当于是【头、右、左】顺序的逆序，因此只需要把先序的想法稍微改变一下，再逆序打印，即可完成后序遍历的非递归实现。

为了实现“逆序”，我们需要另外创建一个收集栈，将原栈打印的东西存起来，最后再将收集栈中的东西一一弹出，即完成了“逆序”

创建一个栈，首先把根节点扔进去，然后每次：

1. 从栈中弹出一个节点 cur
2. 将 cur 压入“收集栈”（对于先序操作中的打印操作）
3. 把 cur 的左孩子压到栈里去，再把 cur 的右孩子压到栈里去（即先左后右压到栈里去）
4. 重复1-3步
5. 依次弹出“收集栈”里的内容

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        stack.append(root)
        res = []
        while(len(stack)>0):
            cur = stack.pop()
            res.append(cur.val)
            if cur.left: stack.append(cur.left)
            if cur.right: stack.append(cur.right)
        return res[::-1] # 注意逆序返回

层次遍历_

需要利用队列来实现二叉树层次遍历的非递归实现。

创建一个队列，首先将根节点放进去，然后进行：

1. 弹出一个节点 cur 并操作（常为存入list）
2. 将 cur 的左节点入队，再将 cur 的右节点入队
3. 重复1-2至队列为空

有的题目可能要求对于每层的节点操作方式不同，那么就会引出另一个问题：如何清晰的知道啥时候该层的节点都弹出完了，有如下两种策略：

1. 每开始新的一层，都记录一个指示该层节点个数的变量，弹出对应数目个，即表示进入下一层（因此队列中不止有一层的节点，是依靠该变量指导 的）
2. 创建一个新的队列，把该层的左右孩子都加入到的新的队列中，直到当前层的节点队列为空，然后把下一层的队列赋值给当前层。（因此队列中只会有一层，为空的时候就是当前层节点全部访问完的时候）

代码参考解法一和解法二，以及从上到下打印二叉树1

例题

举个例子 - 1

如下图

先序遍历：1 2 4 5 7 8 3 6 中序遍历：4 2 7 5 8 1 3 6 后续遍历：4 7 8 5 2 6 3 1 层次遍历：1 2 3 4 5 6 7 8