关于二叉树

二叉树作为树的一种，是一种重要的数据结构，也是面试官经常考的东西。昨天看了一下关于树中的面试题，发现二叉树中的面试题比较常见的题型大概有下面几个：创建一颗二叉树（先序，中序，后序）、遍历一颗二叉树（先序，中序，后序和层次遍历）、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值的全部路径、求某一节点是否在一个树中等等。

再详细的说这些面试题之前，不妨先看一下几种常见的二叉树：

完全二叉树：若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈~~~

满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。

哈夫曼树：又称为最有数，这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。

平衡二叉树：所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

二叉树中的那些面试题

再具体说二叉树中的那些面试题之前，我们先看一下二叉树中的每个节点是什么样的，以及为了完成这些面试题，二叉树中声明的函数原型是什么样的：

二叉树的节点：BinTreeNode

View Code

二叉树原型：BinTree，其中包含了这篇文章中要完成的函数原型的完整声明。 

View Code

2.1 创建一颗二叉树

创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：

下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根。

View Code

2.2 二叉树的遍历

二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的：

View Code

2.3 层次遍历

层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。

View Code

2.4 求二叉树中叶子节点的个数

树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码也是相当的简单，易懂。 

View Code

2.5 求二叉树的高度

求二叉树的高度也是非常简单，不用多说：树的高度 = max(左子树的高度，右子树的高度) + 1 。

View Code

2.6 交换二叉树的左右儿子

交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。

View Code

2.7 判断一个节点是否在一颗子树中

可以和当前根节点相等，也可以在左子树或者右子树中。 

View Code

2.8 求两个节点的最近公共祖先

求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦：

View Code

可以看到这种做法，进行了大量的重复搜素，其实有另外一种做法，那就是存储找到这两个节点的过程中经过的所有节点到两个容器中，然后遍历这两个容器，第一个不同的节点的父节点就是我们要找的节点啦。 实际上这还是采用了空间换时间的方法。

2.9 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）

这道题要找到所有的路径，显然是用深度优先搜索（DFS）啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈，栈中的数据是相反的。看看代码：注意使用的两个栈。

View Code

最后，给出一点测试代码：

View Code

运行结果：

以上内容，只是本人看过的面试题目的一点总结，可能不够全，可能其中的代码也有很多的错误，可能其中的内容有点水，但是我想对那部分即将参加面试的应届毕业生还是有帮助的。。大神们勿喷~~~