输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
首先应该考虑两种特殊情况。只有一个节点和空树的情况时，也符合要求。
那么对于一个序列 S，它的最后一个元素就是根节点的值 x，除掉根之后，留下序列 T，再结合二叉搜索树(BST)的特性，可以将 T 分成两段，前一段（左子树）小于 x，后一段（右子树）大于 x，并且这两段依然也是合法的 BST 后序遍历，那么完美地满足递归的定义。
对于时间复杂度可以表示为T(n)=2xT(n-1)+O(n) ，O(n)是 for 循环占用的时间，两个子问题各占 T(n-1)，那么解出的时间复杂度为 O(nlogn)，空间复杂度取决于递归深度，为 O(logn)。
<<剑指offer2>>
对于一个矩阵，请设计一个算法从左上角(mat[0][0])开始，顺时针打印矩阵元素。
给定 int 矩阵 mat,以及它的维数 nxm，请返回一个数组，数组中的元素为矩阵元素的顺时针输出。
先进行边界检查。
顺时针打印矩阵需要好几圈，那么自然需要循环去打印每一圈。所以首先确定循环结束的条件，这里可以由两种方式来判断结束。第一种是根据输出数组的元素个数是否达到了 n*m 个，第二个是假设每一圈的起点是(start,start)，那么存在以下不等式 colums>startx2 并且 rows>startx2 使得循环成立。
接下来就需要打印每一圈，但是打印每一圈有可能分为需要打印一步，两步，三步，四步。那么第一步从左到右是都需要打印的情况，只要确定起始列号和终止列号即可；如果有必要打印第二步，那么需要保证起始行号要小于终止列号，否则该步没有元素可打印。如果有必要打印第三步，那么此时矩阵至少需要两行两列，所以除了终止行号大于起始行号，终止列号也要大于起始列号。同理，如果需要打印第四步，矩阵至少需要三行两列，因此要求终止行号大于起始行号，终止列号大于起始列号。
算法需要线性遍历每个矩阵元素，因而时间复杂度为 O(nxm)，建立了一个输出数组，空间复杂度为 O(nxm)。
<<剑指offer2>>
打印二叉树，实际上就是考察树的遍历算法，其实就是层序遍历或者说树的广度优先搜索(BFS)。而这个遍历算法的实现就是结合队列来实现。那么下面将会以三种展现形式来打印一颗二叉树。
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
我们可以通过具体的例子模拟输出的过程，那么会发现，它总是拿待输出节点列表的首节点优先输出，而节点总是插入到待输出节点列表尾部，因此很容易知道这是一个”先进先出”的过程，满足队列的特性。因此需要利用队列进行实现。
可以使用普通队列 queue 也可以使用双端队列 deque。
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
遍历依旧和题目一一样，但是需要存储每一层输出的节点到数组中，那么就要先确定当前层需要输出多少个节点。因此，定义一个变量 tobeoutput 表示当前层待输出的节点数。那么该变量就在遍历二叉树的时候自减，然后当变量为零时，表示该层已全部输出完毕，那么就更新该变量下层需要输出的节点数，这个数刚好就是已经在队列中的节点数。
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
要实现打印之字形的二叉树需要利用一对栈配合操作。自己手动模拟一遍就懂了。不需要分奇数层和偶数层了，因为一个栈输出完毕后，才会输出另一个栈中的元素，因此可以以栈不空为条件判断当前需要从那个栈输出元素就行。
由于遍历的时候对二叉树的每个节点仅遍历一次，因此时间复杂度均为 O(n)，空间复杂度主要是由节点值的存储数组所消耗。
注：对根节点 root 需要判空，否则在牛客网上会出现段错误，提示您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起，一定需要处理特殊值的输入，随时注意空指针的情况。
参考
<<剑指offer2>>
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。(单节点的树也属于对称的二叉树特例，其余的二叉树只要沿着根节点所在中心对折，重合节点的值也是相等的)
采用递归遍历树的思想。
首先考虑单节点的情况，它也属于对称二叉树的一种；
然后对于含有左右子树的节点 A 来说，假设，下述节点均存在，则 A 的左节点的左节点等于其右节点的右节点，而 A 的左节点的右节点等于其右节点的左节点，那么就符合对称的规则。之后要判断整颗二叉树是否对称，只需继续递归求解相同问题即可。
递归跳出的条件为：只要一边节点不存在，则该树就不是对称的，否则，如果两边节点都不存在，说明已经遍历完整棵树，此时该树一定是对称的二叉树。
算法主要使用递归遍历二叉树，每个结点只需遍历一次，故时间复杂度为 O(n)。而由于使用了递归，那么最差情况下递归工作栈需要消耗的空间复杂度为 O(n)。
<<剑指offer2>>
画图是在面试过程中应聘者用来帮助自己分析、推理的常用手段。画出一些与题目相关的图形，借以辅助自己观察和思考。比如涉及二叉树、链表、二维数组等问题都可以采用画图的方法来分析。
请完成一个函数，输入一棵二叉树，该函数输出它的镜像。
(镜像就是每棵子树的左右节点交换)
由于我们需要对二叉树的每颗子树进行左右子节点的交换过程，因此，我们利用层序遍历二叉树，然后每棵子树进行操作。
而层序遍历二叉树可以使用递归和非递归(循环)的方式。
对于递归方式，当当前根节点或同时不存在左右子树时递归退出，否则就交换两个子树，若一边子树不存在，也必须交换，接下根节点如果还有右节点或左节点，那么就继续递归下去求解。
对于非递归方式，主要利用队列(本题栈也形，因为它只要对每个节点下的子树进行交换，而与节点顺序无关)来实现，从上到下，从左到右依次将需要进行交换的节点入栈(根节点先入栈)，对于出栈的是叶节点就跳过循环。
算法主要利用层序遍历，每个结点只需遍历一次，故时间复杂度为 O(n)。而无论是使用了递归还是栈，最差情况下空间复杂度为 O(n)。
<<剑指offer2>>