中国做外贸的网站,申请个人主页网站地址,科技 杭州 网站建设,猎头网站怎么做今天我们来介绍的是二叉树的「前序」、「中序」、「后序」、「层序」四种遍历方式如何用代码实现。
还不知道这四种遍历方式原理的可以看另一篇文章#xff1a;二叉树#xff1c;I#xff1e;#xff1a;概念及二叉树的前序遍历、中序遍历、后序遍历原理
1. 相关题目
这…今天我们来介绍的是二叉树的「前序」、「中序」、「后序」、「层序」四种遍历方式如何用代码实现。
还不知道这四种遍历方式原理的可以看另一篇文章二叉树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 res2.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 res2.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 res2.2 迭代解法
2.2.1 前序遍历
我们使用栈来进行迭代过程如下
初始化栈并将根节点入栈当栈不为空时弹出栈顶元素node并将值添加到结果中如果node的右子树非空将右子树入栈如果node的左子树非空将左子树入栈。
由于栈是“先进后出”的顺序所以入栈时先将右子树入栈这样使得前序遍历结果为“根 - 左 - 右”的顺序。
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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)curcur.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 res2.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)curcur.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
