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

[FE-Sadhu]

题目

思路：

思路和 105. 从前序与中序遍历序列构造二叉树 一样，都是找到左子树和右子树的中、后序节点，然后递归。

后序遍历的值的结果 === [[左子树的前序遍历结果]， [右子树的前序遍历结果]，根节点]

中序遍历的值的结果 === [[左子树的中序遍历结果]，根节点，[右子树的中序遍历结果]]

我们方法的定义是，输入一个二叉树的后序遍历结果、中序遍历结果，返回构建好的二叉树的根节点。

所以我们可以先根据 左子树的后序/中序遍历结果 求出左子树，同样再求出右子树，最终拼接上根节点就是我们想要的结果了。

代码实现:

var buildTree = function(inorder, postorder) {
    if(!inorder.length) return null;
    const root = postorder[postorder.length -1];
    const rootIndexInInorder = inorder.findIndex(i => i === root);
    const leftTreeInorder = inorder.slice(0, rootIndexInInorder);
    const rightTreeInorder = inorder.slice(rootIndexInInorder + 1);
    const leftTreePostorder = postorder.slice(0, leftTreeInorder.length);
    const rightTreePostorder = postorder.slice(leftTreeInorder.length, -1);
    const node = new TreeNode(root);
    node.left = buildTree(leftTreeInorder, leftTreePostorder);
    node.right = buildTree(rightTreeInorder, rightTreePostorder);
    return node;
};