题目：重建二叉树

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

二叉树的定义如下：

struct BinaryTreeNode{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x):val(x),left(NULL),right(NULL){}
};

解析

二叉树定义：每个节点最多只能有两个子节点的树。又分为

最大堆：根节点值最大
最小堆：根节点值最小
搜索树：左子节点值小于或等于根节点值，右子节点值大于或等于根节点值
红黑树：任意节点的左右子树中最长路径的长度不会超过最短路径的两倍

二叉树的遍历方式分为

前序遍历：根节点->左子节点->右子节点
中序遍历：左子节点->根节点->右子节点
后序遍历：左子节点->右子节点->根节点
层序遍历(广度优先遍历)：从根到叶分层，每层从左到右遍历

小诀窍：中序遍历可由投影法直观得出。如图所示

对于题中二叉树不难得出

前序遍历为 10 6 4 8 14 12 16
中序遍历为 4 6 8 10 12 14 16
后序遍历为 4 8 6 12 16 14 10

观察发现

前序遍历顺序记录根节点信息，即根节点 10 先于子节点 6 14 遍历
中序遍历记录左右子树范围，即左子树节点 4 6 8 先于根节点 10 遍历，右子树节点 12 14 16 后于根节点 10 遍历
后序遍历倒序记录根节点信息，即根节点 10 后于子节点 6 14 遍历

以前序为主，中序为辅，便可重建二叉树😎。代码如下

BinaryTreeNode* rebuildBinaryTree(int *preOrder, int *inOrder, int length)
{
    if (nullptr == preOrder || nullptr == inOrder || length <= 0)
        return nullptr;
    BinaryTreeNode *pRoot = nullptr;
    BinaryTreeNode *pNode = nullptr;
    for (int i = 0; i < length; ++i)
        if (nullptr != pRoot)
        {
            bool leftNode = false;
            int position = length;
            for (int j = 0; j < length; ++j)
                if (inOrder[j] == pNode->val)
                    position = j;
                else if (inOrder[j] == preOrder[i])
                {
                    leftNode = j < position;
                    break;
                }
            if (leftNode)
            {
                pNode->left = new BinaryTreeNode(preOrder[i]);
                pNode = pNode->left;
            }
            else
            {
                pNode->right = new BinaryTreeNode(preOrder[i]);
                pNode = pNode->right;
            }
        }
        else
            pNode = pRoot = new BinaryTreeNode(preOrder[i]);
        return pRoot;
}

此法使用双重循环，效率甚低。可以使用map将inOrder中的数值对应下标存储，以空间换时间。
不过书中提供了更好的思路（分治法）：既然可得出左右子树包含数值，不妨继续对子树继续进行左右子树划分，由此可先（解决小问题）得出含叶子节点子树，继而（解决大问题）合并子树成较大子树，最终形成二叉树。下为子树分析图片

分治法需递归实现，书中神级代码如下：

BinaryTreeNode* rebuildBinaryTree(int *preOrder, int *inOrder, int length)
{
    if (nullptr == preOrder || nullptr == inOrder || length <= 0)
        return nullptr;
    // 递归传入：左子树起点，左子树终点，右子树起点，右子树终点
    return constructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}
BinaryTreeNode* constructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder)
{
    BinaryTreeNode * pRoot = new BinaryTreeNode(*startPreOrder);
    if (startPreOrder == endPreOrder)
        if (startInOrder == endInOrder)
            if (*startPreOrder == *startInOrder)
                return pRoot;
            else
                throw std::exception("Invalid input");
    int * rootPosition = startInOrder;
    while (*rootPosition != *startPreOrder && rootPosition <= endInOrder)
        ++rootPosition;
    if (rootPosition > endInOrder)
        throw std::exception("Invalid input");
    int leftLength = (rootPosition - 1) - startInOrder;
    int rightLength = endInOrder - (rootPosition + 1);
    if (leftLength > 0)
        // 此处传参范围需参考子树分析图片
        pRoot->left = constructCore(startPreOrder + 1, (startPreOrder + 1) + leftLength, startInOrder, rootPosition - 1);
    if (rightLength > 0)
        // 此处传参需范围参考子树分析图片
        pRoot->right = constructCore((startPreOrder + 1) + leftLength + 1, endPreOrder, rootPosition + 1, endInOrder);
    return pRoot;
}

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可