LeetCode-106-从中序与后序遍历序列构造二叉树

一：题目描述

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

二：示例与提示

示例 1:

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

示例 2:

1 2	输入：inorder = [-1], postorder = [-1] 输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

三：思路

`递归构造二叉树`

中序遍历顺序是，左中右
后序遍历顺序是，左右中
因此，可以通过后序遍历可以先知道，根节点是什么，再在中序中，通过根节点知道左右两区间也就是左右子树
依次遍历就将二叉树构造出来了

根据前序遍历来构造二叉树的具体步骤：中，左，右
- 判断终止条件（递归优先步），当中序遍历数组为空时候，返回空节点
- 找到根节点，对根节点进行操作（中），即找到后序遍历数组中最后一个元素
- 寻找根节点在中序遍历数组中的下标索引index，通过index索引对两个序列数组切割左右子树，也作为递归的新参数
- 分割中序遍历数组，通过slice方法对其进行分割左右区间，注意slice区间范围左闭右开
- 分割后序遍历数组
- 递归处理左右区间(左、右)，node.left，node.right指向左右子树
- 最终返回node

四：代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    //
    const getTree = (inorder, postorder) => {
        //中序遍历数组是要被切割的数组
        //中序遍历数组只剩一个元素返回
        if(inorder.length === 0) return null
        //单层逻辑
        //确定根节点同时删除后序遍历数组中的根节点
        let rootVal = postorder.pop()
        let node = new TreeNode(rootVal)
        if(inorder.length === 1) return node
        //获取根节点元素在中序遍历数组中的下标以便切割
        let index = inorder.indexOf(rootVal)
        //处理中序遍历数组中的左右区间问题
        //左
        //切割数组
        let inorderLeft = inorder.slice(0, index)
        let postorderLeft = postorder.slice(0, index)
        node.left = getTree(inorderLeft, postorderLeft)
        //切割数组
        let inorderRight = inorder.slice(index + 1, inorder.length)
        let postorderRight = postorder.slice(index, postorder.length)
        node.right = getTree(inorderRight, postorderRight)
        return node      
    }
    return getTree(inorder, postorder)
};