面试题6：重建二叉树(剑指Offer)

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

public TreeNode BuildTree(int[] preorder, int[] inorder)
{
    if (preorder.Length == 0 || inorder.Length == 0) return null;
    var indexMap=new Dictionary<int,int>();
    var length = preorder.Length;
    for (int i = 0; i < length; i++)
    {
        indexMap.Add(inorder[i], i);
    }
    TreeNode root = BuildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
    return root;
}
public TreeNode BuildTree(int[] preOrder, int preOrderStart, int preOrderEnd, int[] inOrder, int inOrderStart,
    int inOrderEnd, Dictionary<int, int> indexMap)
{
    if (preOrderStart > preOrderEnd) return null;

    var rootVal = preOrder[preOrderStart];
    var root = new TreeNode(rootVal);
    if (preOrderStart == preOrderEnd) return root;

    var rootIndex = indexMap[rootVal];
    var leftNodes = rootIndex - inOrderStart; 
    var rightNodes = inOrderEnd - rootIndex;

    var leftSubtree = BuildTree(preOrder, preOrderStart + 1, preOrderStart + leftNodes, inOrder, inOrderStart, rootIndex - 1, indexMap);
    var rightSubtree = BuildTree(preOrder, preOrderEnd - rightNodes + 1, preOrderEnd, inOrder, rootIndex + 1, inOrderEnd, indexMap);
    root.left = leftSubtree;
    root.right = rightSubtree;
    return root;
}

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x)
    {
        val = x;
    }
}

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

LeetCode官方解答：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/