面试题 7：重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并输出它的头节点。二叉树节点的定义如下：

struct BinaryTreeNode 
{
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
}

• 由于树的操作会涉及大量的指针，因此与树有关的面试题都不太容易。
• 3 种遍历都有递归和循环两种不同的实现方法，递归实现都比循环实现要简洁很多。
• 我们可以平均在 O(logn) 的时间内，根据数值在二叉搜索树中找到一个节点。
• 需要快速找到最大值或最小值的问题都可以用堆来解决。
• 红黑树：把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。STL 中，set、multiset、map、mutimap 等数据结构都是基于红黑树实现的。
• 考查应聘者分析复杂问题的能力。把构建二叉树的大问题分解成构建左、右子树的两个小问题。确定左、右子树节点的数量，用递归的方法去完成。

Source Code