从前序与中序遍历序列构造二叉树
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
题目分析
（1）构建二叉树包含：root,左子树，右子树
（2）中序遍历inorder：[左|根|右]
（3）前序遍历preorder第一项为根节点：[根|左|右]
（4)const root=new TreeNode(preorder[0]); //每次new都是创建新的根节点
3
/ \
9 20
/ \
15 7
思路（一）
/*** 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(!inorder.length) return nullconst root=new TreeNode(preorder[0]); //创建新根节点const mid=inorder.indexOf(preorder[0]);root.left = buildTree(preorder.slice(1,mid+1),inorder.slice(0,mid))root.right= buildTree(preorder.slice(mid+1),inorder.slice(mid + 1))return root;
};