22. 二叉树的遍历

22. 二叉树的遍历题目描述给出一个n个节点的二叉树请求出二叉树的前序遍历中序遍历和后序遍历。输入描述题目包含多行输入第一行为一个整数 N表示二叉树的节点总数后面将有 N 行对应于二叉树的 N 个节点的信息。每行的数据格式遵循如下规则每行开始是该节点的标识符代表二叉树中具体的一个节点。节点标识符之后是两个数字分别表示该节点的左孩子和右孩子的序号。序号根据输入顺序从 1 开始自动分配即第一个输入的节点序号为 1第二个为 2以此类推。若某个节点的左孩子或右孩子序号为 0则表示该节点不存在相应的左孩子或右孩子。输出描述共三行第一行为二叉树的前序遍历第二行为中序遍历第三行为后序遍历输入示例7F 2 3C 4 5E 0 6A 0 0D 7 0G 0 0B 0 0输出示例FCADBEGACBDFEGABDCGEF提示信息样例输入解释如下 首行数字 7 表示二叉树共有 7 个节点。接下来的行按序提供每个节点的信息格式为标识符 左孩子序号 右孩子序号。节点序号自动从 1 依次递增对应输入的行顺序。例如F 2 3 表示标识符为 F 的节点序号为 1有左孩子序号为 2和右孩子序号为 3E 0 6 表示标识符为 E 的节点序号为 3无左孩子有右孩子序号为 6。由于 F 的右孩子是序号为 3 的节点而 E 的序号刚好为 3所以 F 的右孩子就是 E。实现代码Python:importsysclassTreeNode(object):def__init__(self,val,leftNone,rightNone):self.valval self.leftleft self.rightrightdefmain():linessys.stdin.read().splitlines()idx0nint(lines[idx])idx1#读取所有节点信息创建节点对象tree[None]*(n1)foriinrange(1,n1):informlist(lines[idx].split())idx1valinform[0]l_idxint(inform[1])r_idxint(inform[2])nodeTreeNode(val)# 暂存节点孩子序号tree[i](node,l_idx,r_idx)#绑定父子节点关系rootNoneforiinrange(1,n1):cur,l,rtree[i]ifi1:rootcurifl!0:cur.lefttree[l][0]ifr!0:cur.righttree[r][0]pre_res[]#先序遍历根左右defpre(node):ifnotnode:returnpre_res.append(node.val)pre(node.left)pre(node.right)pre(root)print(.join(pre_res))mid_res[]#中序遍历左根右defmid(node):ifnotnode:returnmid(node.left)mid_res.append(node.val)mid(node.right)mid(root)print(.join(mid_res))post_res[]#后序遍历左右根defpost(node):ifnotnode:returnpost(node.left)post(node.right)post_res.append(node.val)post(root)print(.join(post_res))if__name____main__:main()分析本题核心构建按序号存储节点→分两步绑定关系→确定根节点遍历三种 DFS 遍历的递归模板仅访问顺序不同。二叉树常见的三种创建方式为场景 1按「节点序号 父子序号」输入输入特征节点有唯一序号通过 “左 / 右孩子序号” 关联父子如本题、层序输入带序号创建核心① 用列表按「序号」存储所有节点序号 索引 / 键② 分两步先创建所有节点再遍历绑定父子关系代码模板# 1. 初始化节点列表序号从1开始tree[None]*(n1)# 2. 第一步创建所有节点暂存节点孩子序号foriinrange(1,n1):val,l_idx,r_idx读取输入 nodeTreeNode(val)tree[i](node,l_idx,r_idx)# 3. 第二步绑定父子关系rootNoneforiinrange(1,n1):cur,l,rtree[i]ifi1:rootcurifl!0:cur.lefttree[l][0]ifr!0:cur.righttree[r][0]场景 2按「层序遍历数组」输入含空节点标记输入特征一维数组表示层序遍历-1/None 表示空节点如 [1,2,3,-1,4,-1,5]创建核心用队列辅助按层序逐个创建节点空节点跳过代码模板fromcollectionsimportdequedefbuild_tree(level_order):ifnotlevel_orderorlevel_order[0]-1:returnNonerootTreeNode(level_order[0])qdeque([root])idx1whileqandidxlen(level_order):nodeq.popleft()# 左孩子ifidxlen(level_order)andlevel_order[idx]!-1:node.leftTreeNode(level_order[idx])q.append(node.left)idx1# 右孩子ifidxlen(level_order)andlevel_order[idx]!-1:node.rightTreeNode(level_order[idx])q.append(node.right)idx1returnroot场景 3按「前序 中序遍历」输入重构二叉树输入特征给出前序和中序遍历结果重构二叉树创建核心前序找根中序分左右子树递归构建代码模板defbuild_tree(pre_order,in_order):ifnotpre_orderornotin_order:returnNone# 前序第一个元素是根root_valpre_order[0]rootTreeNode(root_val)# 中序中找根的位置分左右子树root_idxin_order.index(root_val)# 递归构建左子树前序[1:1root_idx]中序[0:root_idx]root.leftbuild_tree(pre_order[1:1root_idx],in_order[:root_idx])# 递归构建右子树前序[1root_idx:]中序[root_idx1:]root.rightbuild_tree(pre_order[1root_idx:],in_order[root_idx1:])returnroot