二叉树＜II＞：二叉树的四种遍历方式代码实现Python3

今天我们来介绍的是二叉树的「前序」、「中序」、「后序」、「层序」四种遍历方式如何用代码实现。

还不知道这四种遍历方式原理的可以看另一篇文章：二叉树＜I＞：概念及二叉树的前序遍历、中序遍历、后序遍历原理

1. 相关题目

这里是 4 道相关题目：

144.二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历

2. 题目解析

2.1 递归解法

由于层次遍历的递归解法不是主流，因此只介绍前三种的递归解法。它们的模板相对比较固定，一般都会新增一个dfs函数：

def dfs(root):if not root:returnres.append(root.val)dfs(root.left)dfs(root.right)

对于前序、中序、后序遍历只需要将res.append(root.val)放在不同位置即可，然后调用这个递归函数就可以了，代码完全一样。

2.1.1 前序遍历

class Solution:def preorderTraversal(self,root:TreeNode)->List[int]:res = []def dfs(root):# 为了让上一级定义的res能在这个函数用nonlocal resif not root:return# 拼接节点res.append(root.val)# 拼接左子树节点dfs(root.left)# 拼接右子树节点dfs(root.right)dfs(root)return res

2.1.2 中序遍历

class Solution:def inorderTraversal(self,root:TreeNode)->List[int]:res=[]def dfs(root):nonlocal res;if not root:return# 左子树dfs(root.left)res.append(root.val)# 右子树dfs(root.right)dfs(root)return res

2.1.3 后序遍历

class Solution:def afterorderTraversal(self,root:TreeNode)->List[int]:res = []def dfs(root):nonlocal resif not root:return# 左子树dfs(root.left)# 右子树dfs(root.right)res.append(root.val)dfs(root)return res

2.2 迭代解法

2.2.1 前序遍历

我们使用栈来进行迭代，过程如下：

• 初始化栈，并将根节点入栈；
• 当栈不为空时：弹出栈顶元素node，并将值添加到结果中；
• 如果node的右子树非空，将右子树入栈；
• 如果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 []stack,res,cur=[],[],rootwhile cur or stack:# 进来一个节点先遍历根节点和左子树while cur:res.append(cur.val)# 进到栈里的都是根节点和左子树的点stack.append(cur)cur=cur.left# 弹出栈顶元素，走到这一步的都是把当前左子树遍历完了tmp = stack.pop()# 将弹出节点的右节点给到当前节点cur = tmp.rightreturn res

2.2.2 中序遍历

和前序遍历的代码完全相同，只是在出栈的时候才将节点tmp的值加入到结果中。

class Solution:def inorderTraversal(self,root:TreeNode)->List[int]:if not root:return []# 初始化res,stack,cur=[],[],rootwhile cur or stack:# 深入左子树，左子树节点先入栈while cur:stack.append(cur)cur = cur.left# 左子树节点先出栈temp = stack.pop()res.append(cur.val)# 深入右子树节点cur = temp.right()return res

2.2.3 后序遍历

按照上面的思想，这次我们反着思考。节点cur先到达最右端的叶子节点并将路径上的节点入栈；
然后每次从栈中弹出一个元素后，cur到达它的左节点，并将左节点看作cur继续执行上面的步骤。
最后将结果反向输出即可。

class Solution:def postorderTraversal(self,root:TreeNode)->List[int]:if not root:return []stack,res,cur=[],[],rootwhile cur or stack:# 先遍历右子树节点while cur:res.append(cur.val)stack.append(cur)cur=cur.righttemp = stack.pop()# 深入左子树节点cur = temp.leftreturn res[::-1] #反向输出

然而，后序遍历并没有按照真正的后序遍历的真实过程执行，下面对真实的过程做实现。

class Solution:def postorderTraversal(self,root:Optinal[TreeNode])->List[int]:if not root:return []res,stack = [],[root]# 为了判断父子节点关系while stack:# 取出一个节点，表示开始访问以该节点为根的子树root = stack.pop()# 如果该节点为叶子节点，或者已经访问该节点的子节点if(not root.left and not root.right) or (root.left == prev or root.right == prev):# 直接访问 res.append(root.val)prev = rootelse:# 否则就顺序把当前节点，右节点、左节点入栈stack.append(root)if root.right:stack.append(root.right)if root.left:stack.append(root.left)return res