分析
1、 前序遍历的第一个点就是根节点,
2、 在中序遍历种找打这个点,假设为i
, 中序遍历分为两部分 左子树0~i-1
右子树i+1~
3、 根据中序遍历确定,前序遍历的左右子树 前i个即为左子树 1~i
右子树i+1~
4、 注意slice的end是不包含的即可
样例
1
/ \
2 3
/ \
4 5
1 2 4 5 3
4 2 5 1 3
取根节点 1 ==>中序遍历 i = 3(下标)
==》 中序遍历 左:425 右 3
==》 前序遍历 左:245 右 3
Code
/**
* 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 rootVal = preorder[0];
const node = new TreeNode(rootVal);
let i = 0;
for(; i < inorder.length; i++){
if(inorder[i] === rootVal) break;
}
node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i)); //前序的前i个数
node.right = buildTree(preorder.slice(i + 1), inorder.slice(i+1));
return node;
};