$101\sim110$是树的系列，做惯了以后会感到蜜汁畅快。果然简单题是成就感的来源啊。
101. 对称二叉树
给两棵树，判断是否对称。思路和上面那题 100. 相同的树 是一样的。还是通过 遍历 和 逐个比较 的方式：
- 对根节点的左右子树分别使用后序遍历(‘左右中’)与前序遍历(‘中左右’)，因为对称树的左子树左结点与右子树右结点应该是一样的，所以两个遍历结果应该是倒序相同的。
- 同样进行递归方式，判断左右子树是否是对称的。
102. 二叉树的层次遍历
对一棵二叉树进行层次遍历。这个没什么好说的，用一个 队列 就可以了，每次出队当前节点，再把当前节点的左右子节点依次入队。
本题有一个注意点是所要求的输出格式不太一样，不是用一个数组输出，而是不同层的节点要放在一个数组中，然后所有数组合并成一个数组来输出。这就要求在出入队操作时还需要知道自己操作的是哪一层的节点。一个可行的解决办法是：建立一个结构体，保存节点指针与这个节点所在的层。当一个节点出队时，发现层数和上一个节点不一样了，说明来到了一个新的层，这个时候要把已经统计的结点数组加入到结果数组中，并把前者清空。
103. 二叉树的锯齿形遍历
这题和 102 题几乎是一样的，唯一不同的是要求按 左到右、右到左、左到右 的顺序来输出 ，一开始想的是根据层数不同在入队的时候就进行左右和右左的顺序入队处理，后来发现这样是不对的，一个更简单并且更好做的方法是：按层次遍历的方法入队，然后对每一个数组，根据它的下标来判断是否进行reverse就可以了。如果数组的下标$\mathrm{i}$满足$\mathrm{i}\%2\neq0$，则将这个数组进行反转。
104. 二叉树的最大深度
没什么好说的，随便一种递归遍历+到边界时更新最大深度即可。
105. 从前序与中序遍历构造二叉树
这道题居然一次过了……简直是我这两天做题以来 最好的feedback ，就像哪本不知名励志文章里说的一样：没有比成功本身对成功更好的催化剂了。
其实本科时候还对重构二叉树很迷惑的，当时想了半天没想出来呢。
好了，考虑前序的遍历过程是’中左右’，而中序的遍历过程是’左中右’，所以我们递归的干下面的事情：
- 找到前序过程中第一个元素，这个元素是当前子树的根节点。
- 在中序过程中找到这个根节点，然后把中序划分成左右两个部分，左边就是左子树，右边就是右子树。
- 根据2中左右子树的长度，把前序第一个元素之后的部分（因为第一个元素是根节点，所以不用考虑它，正如对中序进行划分的时候也不用考虑找到的那个中间节点一样）也划分成两个部分，其中前面的是左子树，后面的是右子树。
- 把3中的左右部分分别传到递归建树的函数中继续建树。
- 上面的步骤进行到划分时的下标$\mathrm{beign}>\mathrm{end}$为止。当然，如果$\mathrm{beign}=\mathrm{end}$，则说明当前的节点是一个叶子节点。
106. 从中序与后序遍历构造二叉树
这个没什么好说的，就是 105 题的翻版，只不过寻找根节点的操作从$\mathrm{preorder}$的第一个元素变成了$\mathrm{postorder}$的最后一个元素而已。不再赘述。
107. 二叉树的层次遍历II
这次就是要求从底部到顶部进行遍历了，其实很简单，就是把正常的层次遍历数组给反转过来就可以了。另外这里还知道一个trick：
对于要输出的二维结果数组，如果有$A=[B, C, D, …]$，其中$B,C,D$是一维数组。
执行$\mathrm{reverse}(A)$之后，只会在二维数组层面对数组进行反转，而不会反转嵌套在里面的一维数组的内容。
即$\mathrm{reverse}(A)=[…, D, C, B]$——$B,C,D$的元素不会进行反转。
值得注意的是，对于 103. 锯齿形遍历 与 107. 层次遍历II ，哪怕程序要求的输出里面没有嵌套深度，我们也需要对深度进行嵌套，因为这些遍历过程需要对每层进行变换。
108. 将有序数组转换二叉搜索树
对一个升序排列的数组，构建它的平衡二叉树。采用二分数组的方式递归创建就可以了：每次取数组区间里面中间的元素作为根节点，然后将左右区间用来创建根节点对应的左右子树。边界条件是区间不存在（此时返回NULL），或者左右区间已经指定到一个值（此时是树的一个叶子节点）。
109. 有序链表转换二叉搜索树
和 108. 将有序数组转换成二叉搜索树 的唯一区别就是从一个升序数组改成了升序链表，而后者的特点在于没法使用index直接定位到中间那个元素。
有两种解题方法：
- 扫一遍链表将内容保存到数组，然后用108的解题方法依葫芦画瓢即可。
- 每次扫描到链表的一半，然后把链表断开，前面的一半传给左子树，后面的一半传给右子树。这样的一个问题是要重复扫描链表来获得中间节点的位置。
因为时间复杂度 想要偷懒 ，实际解题时使用的是第一种方法。
110. 平衡二叉树
判断一棵树是不是平衡二叉树。正常人的第一思维应该是这样的：
要判断这个树是不是平衡二叉树，就要判断它的两个左右子树深度相差值是否为1，也就是分别求这两个子树的最大深度$d_1, d_2$，如果有$\mathrm{abs}(d_1-d_2)\leq 1$，则说明这棵树是平衡的。接下来继续递归求这棵树的两个子树是否是平衡二叉树。
这个思路没有问题，但是时间复杂度会很高，因为在求一棵树的深度时是 从上往下 迭代来求的，特别地，深度为3的子树在判断深度为1已经深度为2的树是否是平衡二叉树时进行了两次扫描。出现这个问题的原因是 递归中采用了前序遍历的思想 ：我先求中间的节点是否满足条件，再求两棵子树是否满足条件，这样会导致重复计算。
为了减少时间复杂度，可以采用 后序遍历 的思想，即：先判断两棵子树是否平衡，并且在判断时使用引用传参的方式获得这两棵子树的深度。具体地：
如果当前节点为空，则直接返回true，因为空树肯定满足平衡二叉树的条件。如果当前节点不为空，说明节点至少有一棵子树，此时先求当前节点的两棵子树是否是平衡二叉树，并且在计算过程中使用参数传递的方式获得两棵子树的深度。如果两棵子树都是平衡二叉树，并且深度相减$\leq1$，就说明当前的节点为根的树是一棵平衡二叉树，此时设置这棵树本身的深度为$\mathrm{max}(d_1,d_2)+1$，返回true即可。当然，其它所有情况都返回false。