【题目链接】ybt 1981：【18NOIP普及组】对称二叉树洛谷 P5018【NOIP2018 普及组】 对称二叉树【题目考点】二叉树【解题思路】先求出二叉树中各子树的结点数遍历二叉树，判断每个子树是否是对称二叉树判断一个二叉树是否是对称二叉树：对称变换：将该树中所有结点的左右子树交换。显然，一棵树经过两次对称变换后，会变为原来的树。两树对称：如果树1经过对称变换可以变为树2，那么称树1与树2对

中序遍历的同时做计数，判断当前遍历到的结点的值是不是x，如果是，则记录当前的计数。默认各结点的值不同，则不会再次遍历到值为x的结点。可以默认各结点的值是不同的。

层次遍历序列的下一个元素就是左子树的根结点，可以将左子树的中序遍历序列拆为两部分。再下一个元素就是右子树的根结点，可以将右子树的中序遍历序列再拆为两部分。层次遍历序列第一个元素，一定的整棵树的根结点。在中序遍历序列中找到该根结点元素，其左边就是左子树的中序遍历序列，右边就是右子树的中序遍历序列。为了使每次在层次遍历序列中取到的元素对应中序遍历序列的根结点，那么每次得到的中序遍历序列也得像做层次遍历

ybt 1378：最短路径(shopth)邻接矩阵中表示两顶点不连接的’-‘，在其它输入的情况下未必是’-'。各求最短路径算法适用情况：scanf的返回值是正确读取变量的个数对于如果输入1 2，正确读入两个变量，返回2。如果输出1 -或- 1，正确读入1个变量，返回1。注意：如果用%d读入字母，无法正确读入，输入流中会一直有该字母的信息，需要对输入流做清空后，再进行后面的输入。本题图中可能存在负权

【题目链接】ybt 1342：【例4-1】最短路径问题【题目考点】1. 图论 最短路径图中有V个顶点E条边，最短路径算法时间复杂度：朴素Dijkstra算法：O(V2)O(V^2)O(V2)Dijkstra堆优化算法：O(ElogE)O(ElogE)O(ElogE)SPFA算法：一般情况下O(kE)O(kE)O(kE)，k为顶点度（出度）的平均值，最坏情况下O(VE)O(VE)O(VE)Floyd

搜索时，带一个参数表示当前的层数，每搜索深入一层，该层数加1。如果该结点是叶子结点，那么更新最大层次数（也可以搜索到任意结点时都一次更新），最后输出最大层次数。

如果这样建图：每个人是一个顶点。如果a是b的父辈，那么有一条从a到b的有向边。根据拓扑排序的定义：如果从a到b有一条路径，那么b在拓扑排序中在a的后面。那么这个图的拓扑排序可以满足题目对所求的序列的要求。要求序列中“每个人的后辈都比那个人后列出”。因此这是个拓扑排序模板题，建图，求拓扑排序。

该题意为：为每个结点都设一个长度：叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。接着按照先序遍历的顺序，每行输出一个结点的值，这个结点的长度是几，这一行就输出几个字符。用preOrder函数递归输出每个结点，每个结点输出的次数是其长度。在结点中设成员变量length，表示这个结点的长度。用calcLen函数递归求出每个结点的长度。

注意在遍历顺序存储结构的树的时候，临时求出的下标可能会很大（因为每次都会乘以2），所以数组尽量开得大一些（比如最后一个结点的地址是1000，那么要把数组长度开成2000多），也可以先记录整个顺序存储结构tree数组中最后一个元素的下标tn，如果访问到的下标超过tn，那么这次访问无意义，直接返回。如果使用非递归的方法做遍历，就可以使用函数的返回值来表示该树是否对称，效率更高。遍历整棵树（使用哪种遍历

ybt 1340：【例3-5】扩展二叉树用getchar()或cin.get()每次读取一个字符。先序序列的格式为：可以用递归的方法构建二叉树：