一举满分。。不枉我肝了几个月的题。

第一题其实确实最简单,却诡异地通过率最低。。4%也是醉了。
猜测可能是PAT之前有几次在第一题挖坑,大家被挖怕了。
然后这题确实不好测试,测试用例不给复制。。见鬼那么长又不可能自己对着打一遍。
我是自己瞎编了个图形输入,然后复制粘贴出所需输入。。来测试。

第二题又是熟悉的链表。这次题目堵住了以前以往同类题目可以偷偷转换为顺序结构暴力解掉的小漏洞..
老老实实写链式结构反转。两个迭代变量搞即可,考逻辑思维和代码基本功。

第三题存储关系用邻接矩阵也不会爆空间,直接双重for遍历也没爆时间。。。
可以配合哈希表(unordered_set)提升查询速度,
感觉有点水。

第四题Cartesian Tree,结合了堆和树两个知识点。
我们在学习二叉树时,知道根节点和中序遍历顺序,就可以构建整个树。
这里其实对于每一颗树(包括其子树),最小的数就是根节点,这是由最小堆的性质保证的,而输入给出了中序遍历,自然可以构建出整棵树。
解析建树采用递归写法,层序输出采用队列来BFS。