剑指 Offer 07. 重建二叉树

描述

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

示例 1：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7] 返回如下二叉树： 3
/ \
9 20
/ \
15 7

题解

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，最后遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
小结：看输出父节点的顺序，就确定是前序、中序，还是后序
这道题的思路来源于B站up小美算法的这个视频

/**
 * 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[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length) return null
    // 前序数组的第一个值就是根节点
    let root = new TreeNode(preorder[0]) 
    // 找到根节点在中序数组里的索引
    let index = inorder.findIndex(item => item === root.val)
    root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index))
    root.right = buildTree(preorder.slice(index + 1, preorder.length), inorder.slice(index + 1, inorder.length))
    return root
};