二叉树经典面试题
首先给出五道关于二叉树的面试题，题目很简单，这里会给出简单分析，具体代码，这里只给出最优解法。
◆找出二叉树中最远结点的距离
◆由前序遍历和中序遍历重建二叉树
◆判断一棵二叉树是否为完全二叉树
◆求二叉树中两个结点的最近公共祖先
◆将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
找出二叉树中最远结点的距离
首先需要考虑一下，二叉树中什么距离是最远距离。以根节点为轴，左右子树的最大深度？当然这只是一部分。准确地说，最大深度是以根节点为轴，左右子树的最大深度之和与以各个子树的根节点为轴左右子树的最大深度之和的较大值。
虽然有点绕，看下图就会明白。
思路一：解决这个问题最直接的方式就是遍历。对每个结点求深度，之后再与保存的最大深度max_depth进行对比，但对于O(n^2)的时间复杂度，我们还是选择能避免就避免，这应该是一种比较糟糕的时间复杂度。
思路二：针对思路一，可以发现，我们重复了大量的遍历工作。对每一个结点求深度，对最深的一个结点遍历了n^2次，没有线索化过的二叉树遍历，最常用的是递归方法，因此，我们可以仅仅通过一次递归，同时得到该结点的深度和以该节点为根的子树的最大距离。当然，由于深度是相对整个遍历过程的，因此在递归过程中，它应该是以引用的方式进行传递，我们这里不需要将深度也作为一个参数进行传递，原因很简单，深度完全可以在递归的时候用返回值接收，这也解决了对左右子树深度的比较选取的过程中多余创建出的变量。
int MaxDistance()
{
if (_root == NULL)
return 0;
int max = 0;
_MaxDistance(_root, max);
return max;
}
int _MaxDistance(Node* cur, int& max) // 只返回深度
{
if (cur == NULL)
return 0;
int leftDepth = _MaxDistance(cur->_left, max);
int rightDepth = _MaxDistance(cur->_right, max);
if (leftDepth + rightDepth > max)
max = leftDepth + rightDepth;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
代码看上去很简单，这里巧妙之处在于在MaxDistance()函数中，我们没有用它调用的_MaxDistance()函数的返回值，该函数返回值的作用，仅仅是为了提供递归返回使用。我们需要的max_distance是通过传递引用的方式获取的。
由前序遍历和中序遍历重建二叉树
这道题应该是网上做烂的题目，这里只是重新提一下，因为它并没有什么建档方法可言。
我们需要考虑，前、中、后序遍历三种方式遍历结果有什么特点。
前序遍历：第一个元素必然是根节点，扩展一点将，如果我们从前序遍历的序列中取出的一段属于某个子树的前序遍历段，那么该子序列的第一个结点也将是该子树的根节点。
中序遍历：中序遍历由于是先左后根，最后再右的顺序，因此，当我们知道某个结点为跟结点的话，那么它的左右两侧分别是左子树和右子树的中序遍历序列。同上，也扩展一点将，只要可以找到某一段子树中序遍历序列的根节点，那么该序列中，跟结点的左右两侧序列也是该子树的左右子树。
后续遍历：后续遍历的特点是遍历完左右结点之后再遍历跟结点。和前序遍历的区别就在于把根节点放到了最后访问，因此，两种遍历的结果类似，只不过需要从后向前依次取元素。也就是说，最后一个元素，是当前树的根节点。
经过上面的分析，我们可以得出一个这样的结论，如果我们想重建二叉树，我们至少需要两种遍历的序列，而且必须要有中序遍历序列。
接下来我们讨论如何利用前序和中序遍历的结果重建二叉树。大致可分为以下四步：
1. 用前序序列的第一个结点作为根结点;
2. 在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);
3. 根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;
4. 对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。
下来看实现代码。
typedef BinaryTreeNode<char> Node;
Node* ReBuildTree(const string preorder, const string inorder)
{
if (preorder.empty())
return NULL;
char root_value = preorder[0];
Node* node = new Node(root_value);
size_t index = inorder.find(root_value);
string left_preorder = preorder.substr(1, index);
string left_inorder = inorder.substr(0, 3);
string right_preorder = preorder.substr(index + 1, preorder.size() - index - 1);
string right_inorder = inorder.substr(index + 1, inorder.size() - index - 1);
node->_left = ReBuildTree(left_preorder, left_inorder);
node->_right = ReBuildTree(right_preorder, right_inorder);
return node;
}
void InOrder(Node* node)
{
if (node == NULL)
return;
InOrder(node->_left);
cout << node->_data << " ";
InOrder(node->_right);
}
仔细观察可以发现，这里使用的容器是string，我这里选用string作为容器，是因为string有自带的查找某个元素的功能，同时可以实现部分截取，方便构建子序列，缺点就是每个结点中key的类型只能是字符。当然，这里也可以选用vector等其他容器，只不过vector没有内置的Find函数，因此在中序遍历序列中找根节点的时候需要进行遍历，vector构建子序列时也并不复杂，可以通过迭代器区间直接构造一个vector对象。这里点到为止。
判断一棵二叉树是否为完全二叉树
首先需要知道的是什么是满二叉树。若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
判断一棵树是不是满二叉树，就不能再像之前那样，递归去遍历，因为递归是在走深度，所以解决这一问题，需要借助queue完成层序遍历。
我们简单的层序遍历是先将根节点入队列，之后依次访问队列的front结点，访问完成，将front结点pop，同时将左右不为空的子节点入队列，直到队列为空。这一点应该没有太大问题。回想一下，我们在简单层序遍历的时候，注意了什么问题？如果子结点为NULL，则不入队列，防止下次对空结点进行访问 。
回到我们一开始的问题，判断一棵二叉树是否为满二叉树。这里在简单层序遍历上做一些处理，先不考虑队列的问题，当我们简单地在走层序遍历过程中，当碰到一个结点为NULL时，如果之后都是空结点，那么该二叉树为完全二叉树，否则，不满足完全二叉树。
因此，要实现这个逻辑，就不能只是简单地把非空结点入队列，所有结点都需要入队列，当front变为NULL时，表示读取到了一个空结点，此时，它的子节点之前的所有结点都已经入队列，当队列中还存在空结点，则该树不满足满二叉树。
代码实现如下：
bool IsFullBinaryTree()
{
if (_root == NULL)
return true;
queue<Node*> que;
que.push(_root);
Node* front = NULL;
while (front = que.front())
{
que.push(front->_left);
que.push(front->_right);
que.pop();
}
while (!que.empty())
{
if (que.front() != NULL)
return false;
que.pop();
}
return true;
}
求二叉树中两个结点的最近公共祖先
第一次看到这道题，感觉无从下手，后来仔细想想，不是废话么，只告诉了要找最近公共祖先，二叉树的特点都不知道，怎么找......没办法，分情况看。
情况一：搜索二叉树
这应该是最简单的情况了，搜索二叉树始终满足根结点大于左孩子，小于右孩子。那他们的公共祖先的key值就必然介于两个结点之间。即
(root->_data >= node1->_data && root->_data <= node2->_data) ||(root->_data >= node2->_data && root->_data <= node1->_data)
因此，这样一来就简单了很多，代码实现如下：
typedef SearchTreeNode<int> Node;
Node* FindParent_SearchTree(Node* node1, Node* node2, Node* root)
{
if (root == NULL)
return NULL;
if (node1 == NULL)
return node2;
if (node2 == NULL)
return node1;
while (1)
{
if(root === NULL)
assert(false);
if ((root->_data >= node1->_data && root->_data <= node2->_data)
|| (root->_data >= node2->_data && root->_data <= node1->_data))
{
return root;
}
else if (root->_data > node1->_data)
root = root->_left;
else
root = root->_right;
}
}
最开始的判断条件是为了防止BUG的出现的。因为这种做法有个缺陷，如果两个结点不再树中呢？但是再想一想，我传递的参数是 Node* ，该结点一定是通过Find()函数或其他可以返回Node* 类型的函数返回的，如果不存在某个结点，这里参数传递一定是NULL，因此这里添加了if判断。
情况二：带父指针的二叉树
如果说一个该二叉树结构中有父指针，那么这道题处理起来就应该容易的多。有父指针，意味着我可以从下向上去遍历，沿着父节点的路径直到走到根节点。那问题就转化为求两个单链表的交点CrossNode。
求解单链表的交点解法有两种，一就是对两个单链表进行遍历并求出长度，然后再重新遍历，第二次遍历时，较长的单链表的指针要先走长度差次，当两个指针相同时，表明相遇，如果走到NULL，则只有一种情况，这两个结点不在一棵树内。第二种方法就是构建环。让根节点的父指针parent指向其中一个结点，以另一个结点为头，判断链表是否带环。
这里给出通过找交点找到最近公共结点的代码：
Node* NearestParent(Node* Node1, Node* Node2)
{
if (_root == NULL)
return NULL;
if (Node1 == NULL || Node2 == NULL)
assert(false);
int length2 = 0;
int length3 = 0;
Node* cur1 = Node1;
Node* cur2 = Node2;
while (cur1 != NULL)
{
length2++;
cur1 = cur1->_parent;
}
while (cur2 != NULL)
{
length3++;
cur2 = cur2->_parent;
}
Node* long_List = NULL;
Node* short_List= NULL;
if (length2 > length3)
{
long_List = Node1;
short_List = Node2;
}
else // length2 <= length3
{
long_List = Node2;
short_List = Node1;
}
int distance = abs(length2 - length3);
while (distance--)
{
long_List = long_List->_parent;
}
while (long_List != NULL)
{
if (long_List == short_List)
return long_List;
long_List = long_List->_parent;
short_List = short_List->_parent;
}
return NULL;
}
情况三：任意一棵不带父节点的二叉树
这种情况应该是最复杂的。
这里给出一种新思路，应该很少用过的。在C++里面，有个结构体叫pair，是库里封装好的，提供了两个成员，通过这种方式，我们可以一次返回多个值。给出pair的定义。
template<classT1,classT2>structpair
{typedefT1 first_type;typedefT2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2()) {}
}
给这个东西有什么用呢？
继续回到我们一开始的问题。我们要找两个结点的最近父节点。当然一层嵌套一层地遍历二叉树也有可能得出结果，但效率太低，至少是O(n^2)的时间复杂度。我们得到什么信息的时候，可以确定一个结点是他们的公共祖先？如果我们可以得到信息，在该结点的左右子树中找到了两个结点，那这个结点一定是他们的父节点（先不考虑是否为最近）。
换句话说，我们需要在一个结点出得到的信息，应该是在它的左右子树中遍历到的两个结点的个数。同时因为要采用的是递归遍历，因此我们需要返回该结点。怎么解决“最近”的问题呢？递归给我们提供了方便，只要在一开始进行一次判断即可。
代码实现如下：
Node* NearestParent(Node* Node1, Node* Node2)
{
if (_root == NULL)
return NULL;
if (Node1 == NULL || Node2 == NULL)
assert(false);
pair<Node*, int> ret = NodeNearestParent(_root, Node1, Node2);
return ret.first;
}
pair<Node*, int> NodeNearestParent(Node* root, Node* node1, Node* node2)
{
if (root == NULL)
return pair<Node*, int>(NULL, 0);
pair<Node*, int> left_pair = NodeNearestParent(root->_left, node1, node2);
pair<Node*, int> right_pair = NodeNearestParent(root->_right, node1, node2);
if (left_pair.second == 2)
return left_pair;
if (right_pair.second == 2)
return right_pair;
int x = 0;
if (root == node1 || root == node2)
x = 1;
return pair<Node*, int>(root, left_pair.second + right_pair.second + x);
}
pair结构题中保存的两个对象，第一个是当前结点，另外一个是在它左右子树中找到的两个结点个数，当然包括了它自己。一旦当某次发现，该结点的second为2时，表明该结点就是我们要找的最近父结点。这里采用的依旧是后续遍历的方式。
将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
这道题应该和二叉树的线索化类似，不过有一点不同的是，线索化只是针对空结点而言的，只有当二叉树中某个指针为空，才需要改变它的指向。
对于二叉搜索树而言，它的中序遍历序列就是有序的，因此，这里依旧采用的是中序遍历来改变它。将二叉树转换为双向链表，其实就是让左孩子指针指向该结点的前一个结点，右孩子指针指向下一个结点。因此遍历的时候，需要两个指针，prev和cur。
还有一点需要注意，转换为双向链表之后，二叉树的结构即不复存在，我们就不能再通过根节点去遍历二叉树，因此这里在将二叉树转换为双向链表之前，首先要做的是保存它的最左结点，因为它的最左结点是双向链表的头结点。
代码实现如下：
Node* BinaryTreeToList()
{
if (_root == NULL)
return NULL;
Node* head = _root;
while (head->_left != NULL)
{
head = head->_left;
}
Node* prev = NULL;
_Translate(_root, prev);
return head;
}
void _Translate(Node* root, Node*& prev) // prev要传递引用
{
if (root == NULL)
return;
_Translate(root->_left, prev);
root->_left = prev;
if (prev)
prev->_right = root;
prev = root;
_Translate(root->_right, prev);
}
这就是这五道面试题，解题思路和代码已经给出。可以发现，递归是降低二叉树时间复杂度的有效方式，时间复杂度一般可以用O(n^2)降低到O(n)，缺点就是带来了O(logN)的空间复杂度，logN是非常小的复杂度，相对来说，递归解决二叉树在绝大多数情况下，是一种相对较为优的解法。
同时，这里加入了一种新的思想，就是pair，如何给pair的两个成员分配合理的类型和功能，这个是需要考虑的问题，但不得不说，有些情况下，pair可以带来意想不到的效果。