1. 题目

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

2. 解题

• 树的遍历

与线性结构（如数组 链表 队列）不同，树有多种遍历的方式。常见的有三种：

源于维基百科

(a)中序遍历（左，中，右）：2 7 5 6 11 2 5 4 9
(b)前序遍历（中，左，右）：2 7 2 6 5 11 5 9 4
(c)后序遍历（左，右，中）：2 5 11 6 7 4 9 5 2

以中遍历为例：
1.遍历左子树 inOrder(left-subtree)
2.访问父节点
3.遍历右子树 inOrder(right-subtree)

var output;
function inOrder(root){
    if root{
        inOrder(root.left);
        output = output + string(root.val);
        inOrder(root.right);
    } 
}

中序遍历可以用于通过二分查找树(BST)构造一个非降序的序列，后序遍历可用于删除树

• 通过中序 + 前序/后序 构建一颗二叉树

1. 从前序中取一个值，并将preIndex + 1
2. 以该值构建一个节点tNode
3. 找到该值在中序中的index，记为inIndex
4. 回溯法调用buildTree函数，将inIndex之前的标记为左子树，之后的标记为右子树

var preIndex = 0;
function buildTreeHelper(pre,vin,strt,end){
    if (strt > end){
        return null;
    }
    const tNode = new TreeNode(pre[preIndex]);
    preIndex += 1;
    
    if (strt === end){
        return tNode;
    }
      
    const inIndex = vin.findIndex(x => x === tNode.val);
    
    tNode.left = buildTreeHelper(pre,vin,strt,inIndex - 1);
    tNode.right = buildTreeHelper(pre,vin,inIndex + 1,end);
    return tNode;
}