题目

leetcode原题链接

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

示例 1:

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

示例 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 保证是树的后序遍历

思路

• 后序数组的最后一个元素就是当前节点，以它为切割点来切割中序数组，就可以得到中序的左数组（子树）和右数组（子树），然后根据切割后的中序数组来切割后序数组。然后再递归中序左数组和后序左数组，中序右数组和后序右数组。
• 递归函数的参数就是中序数组和后序数组，返回值是一个节点，对于最外层递归函数而言就是二叉树的根节点。
• 递归的返回条件：遇到两个数组为空，返回空节点。
• 单层递归逻辑：以传入的后序数组的最后一个值构造一个节点作为中间节点，然后在中序数组中寻找与该值相等的点作为切割点，切割得到中序左数组和中序右数组。然后根据中序数组的切割索引且后序数组得到后序左数组和后序右数组。递归两个做数组得到左节点（左子树），递归两个右数组得到右节点（右子树），让中间节点指向左右子节点。

代码

var buildTree = function(inorder, postorder) {

    function traversal(inorder , postorder){
        if(postorder.length === 0) return null    //返回空节点

        const val = postorder.pop() //中间节点的值
        const node = new TreeNode(val)  //当前中间节点

        // 在中序数组中寻找切割点
        for(var sep = 0 ; sep < inorder.length ; sep++){    //用var声明sep在外部可以访问到
            if(inorder[sep] === val) break
        }

        // 切割得到4个数组
        let leftInorder = inorder.slice(0 , sep) , rightInorder = inorder.slice(sep + 1)
        let leftPostorder = postorder.slice(0 , sep) , rightPostorder = postorder.slice(sep)

        node.left = traversal(leftInorder , leftPostorder)
        node.right = traversal(rightInorder , rightPostorder)

        return node
    }
    
    return traversal(inorder , postorder)
};

精简一下代码

var buildTree = function(inorder, postorder) {
    if(postorder.length === 0) return null    //返回空节点

    const val = postorder.pop() //中间节点的值
    const node = new TreeNode(val)  //当前中间节点
    const sep = inorder.indexOf(val)    //在中序数组中寻找分割点索引

    node.left = buildTree(inorder.slice(0 , sep) , postorder.slice(0 , sep))
    node.right = buildTree(inorder.slice(sep + 1) , postorder.slice(sep))

    return node
};

当然这里每一层递归都创建了四个新的数组，比较耗费时间和空间，可以改为索引的形式来切割。

关注我的专栏，每天更新三道leetcode题解，一起变强！