剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例子：

	前序遍历 preorder = [3,9,20,15,7]
	中序遍历 inorder = [9,3,15,20,7]

输出：

	    3
       / \
      9  20
        /  \
       15   7

首先我们需要了解一下二叉树的前中后序遍历的规则
1、前序遍历：中左右
2、中序遍历：左中右
3、后序遍历：左右中
上面的规则很简单我们只需要根据中的位置判断就行，左始终是在右的左边，反正右始终在左的右边

解法1：递归
思路分析：首先我们算法首先需要判空，同时递归也需要首先找到结束递归的点，在这个题目中结束的点就是两个形参为空，根据我们上面了解到的规则，我们可以总结出，前序遍历的第一个值就是二叉树的根结点，后续遍历的中间节点是数的根节点，所以我门使用前序遍历的第一个参数，去和中序遍历的各个节点对比，找到相同的那个，找到的这个值的左边是左子树，右边的都是又子树，以此类推我们就可以总结出递归规则

        let preorder = [3, 9, 20, 15, 7]; // 前
        let inorder = [9, 3, 15, 20, 7]; // 中

         function TreeNode(val) {
    
             this.val = val;
             this.left = this.right = null;
         }

        function buildTree(preorder, inorder) {
    
            // 判空
            if (!preorder.length || !inorder.length) {
    
                return null;
            }

            const rootVal = preorder[0];
            const node = new TreeNode(rootVal);

            let i = 0;
            for ( i = 0; i < inorder.length; i++) {
    
                if (inorder[i] === rootVal) {
    
                    break;
                }
            }
			// 这里寻找一个数在数组中的位置，方法很多，就不一一列举了
            node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i))
            node.right = buildTree(preorder.slice(1 + i), inorder.slice(i + 1))
            return node
        }