106 从中序和后序遍历构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]

题解

本题关键点从中序遍历还是后序遍历切入，首先必须要从后序遍历切入因为后序遍历最后一个节点肯定是跟节点，然后找到根节点在中序遍历的位置，然后就能把中序遍历分为两个部分，与此同时，也可以把后序遍历分割为两个部分，后序遍历的左半部分长度是中序遍历左半部分的长度，右半部分就是中序遍历的右半部分的长度。

var buildTree = function(inorder, postorder) {
    if(!inorder.length) {
        return null
    }
    const rootValue = postorder[postorder.length - 1]
    const root = new TreeNode(rootValue)

    const indexOfRootValueForInorder = inorder.findIndex(one => one === rootValue)
    const inorderLeft = inorder.slice(0, indexOfRootValueForInorder)
    const inorderRight = inorder.slice(indexOfRootValueForInorder + 1)
    const postorderLeft = postorder.slice(0, inorderLeft.length)
    const postorderRight = postorder.slice(inorderLeft.length, postorder.length - 1)

    //console.log('new values', indexOfRootValueForInorder, inorderLeft, inorderRight)
    //console.log('new values2', postorderLeft, postorderRight)

    root.left = buildTree(inorderLeft, postorderLeft)
    root.right = buildTree(inorderRight, postorderRight)

    return root
};