1. 求两个节点的最近公共祖先；

2. 求二叉树中最远的两个节点的距离；

3. 由前序遍历和中序遍历重建二叉树（如：前序序列：1 2 3 4 5 6 - 中序序列 ：3 2 4 1 6 5）；

4. 判断一棵树是否是完全二叉树 ；

5. 将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向；

6.求二叉树的宽度；

7. 判断一棵二叉树是否是平衡二叉树；

8.判断一颗二叉树是否是另一颗树的子树。

求两个节点的最近公共祖先可分为三种情况，分别为：

（1）搜索二叉树，根据搜索二叉树的性质，左子树的所有节点比根节点小，右子树的所有节点比跟节点大。

如果两个节点都比根节点小，则递归左子树 ；
如果两个节点都比跟节点大，则递归右子树 ；
否则，两个节点一个在左子树，一个在右子树，则当前节点就是最近公共祖先节点。

（2）三叉链，二叉树节点有指向父节点的指针。首先给出node1的父节点node1->_parent，然后将node1的所有父节点依次和node2->parent作比较，如果发现两个节点相等，则该节点就是最近公共祖先，直接将其返回。如果没找到相等节点，则将node2的所有父节点依次和node1->_parent->_parent作比较......直到node1->_parent==NULL。代码如下：

该算法时间复杂度为O(n^2)，可用另一种O(n)的算法：

给定的两个节点都含有父节点，因此，可将这两个节点看做是两个链表的头结点，将求两个节点的最近公共祖先节点转化为求两链表的交点，这两个链表的尾节点都是根节点。

（3）普通二叉树，这种情况可采用与搜索二叉树类似的解法

 从根节点开始遍历，如果node1和node2中的任一个和root匹配，那么与root匹配的节点就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先.  如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

上述方法时间复杂度为O（N^2），下面的方法时间复杂度为O（N）,但是需要额外的空间来存储路径。

1) 找到从根到node1的路径，并存储在一个向量或数组中。
2)找到从根到node2的路径，并存储在一个向量或数组中。
3) 遍历这两条路径，直到遇到一个不同的节点，则前面的那个即为最低公共祖先.

 第一种情况最远的两个节点的距离为它们到根节点的路径长度之和，又有可能距离最远的两个节点之间的路径不经过根节点，如图所示：

所以不要考虑不全，直接用两个子树的的高度相加来表示最远的两个节点的距离。有两种方法求解：

还是要借助两个子树的高度求解，但是要递归整棵树，如果子树中出现第二种情况要更新最大距离，时间复杂度为O（N^2）。

另一种时间复杂度为O（N）的解法：

这个题是要用一颗二叉树的前序遍历序列和中序遍历序列，如：前序序列：1 2 3 4 5 6 - 中序序列 ：3 2 4 1 6 5，来重新构建二叉树。可以利用前序序列和中序序列中根节点的位置特性作为重建依据。图示解析过程如下：

创建右子树的方法与左子树的方法完全相同。当 prev 遍历完前序序列，即二叉树创建完成。代码如下：

完全二叉树： 前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。

这是一个层序遍历非递归法的变型题，同样要借助额外空间来临时存储节点。按照层序遍历二叉树，找到第一个只有非满结点（这个节点只有两种情况，孩子为空或者只有左没有右），如果之后的节点还有非满结点，则不是。

第二种思路：将所有的结点全部押入队列中，每次判断队列的头如果队列头为空了则跳出循环，如果此后队列中还有元素则不是完全二叉树。

与二叉树的线索花化雷同

所谓二叉树的宽度是指：二叉树各??节点个数的最大值。

我们知道层序遍历二叉树是使用 queue 来实现的：每次打印一个节点之后，如果存在左右子树，则把左右子树压入 queue，那么此时的队列中可能既包含当前层的节点，也包含下一层的节点。

而我们要求的是对于特定某一层的节点的个数，因此我们需要从头结点开始，记录每一层的个数，对于当前层的每一个节点，在弹出自身之后把其左右子树压入 queue，当把当前层全部弹出队列之后，在队列中剩下的就是下一层的节点。然后比较队列的size和之前得到的maxWidth，取最大值即为队列的宽度。最终队列为空，得到的maxWidth就是二叉树的宽度！

二叉树中每一个节点的左右子树高度之差均小于2即为平衡二叉树。那么当一颗二叉树的所有子树都是平衡二叉树时，它本身必定为平衡二叉树，用此思想可递归判断二叉树是否是平衡二叉树。代码如下：

这种方法借助左右的高度比较来确定是否为二叉树，需多次遍历二叉树，时间复杂度为O（N^2）。下面是一种O（N）的算法：

判断一颗二叉树是否是另一颗树的子树。

 先在找二叉树里找根节点，找到之后判断后续的节点是否相等，如果相等，则为子树。