105. 从前序与中序遍历序列构造二叉树

做法

• preorder 数组的第一项肯定是根节点 —— 因为前序遍历的顺序是 [根| 左|右 ][根∣左∣右]。
• 由根节点，在 inorder [左 | 根 | 右][左∣根∣右] 中划分出左、右子树的 inorder 序列。
• 通过 inorder 中左右子树的节点个数，在 preorder 中确定左、右子树的 preorder 序列。
• 得到左、右子树的 preorder 和 inorder 序列，就能递归构建左右子树。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder.length || !inorder.length) return null;
    const root = new TreeNode(preorder[0]),rootIndex = inorder.indexOf(preorder[0])
    root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex))
    root.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1))
    return root
};