根据一棵树的前序遍历与中序遍历构造二叉树。
思路:
1.根据前序数组,找到根节点
2.根据中序数组中的根节点,找到左子树的长度
3.根据左子树的长度,找到左右子树的前序数组和中序数组
4.递归调用,直到前序数组为null
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var buildTree = function(preorder, inorder) {
//建立一个哈希表,从中查找数组下标
let map = new Map();
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i],i)
}
const helper=(p_start,p_end,i_start,i_end)=>{
if(p_start>p_end) return null
let root=preorder[p_start]
let node = new TreeNode(root)
let mid=map.get(root)
let leftNum=mid-i_start
node.left=helper(p_start+1,p_start+leftNum,i_start,mid-1)
node.right=helper(p_start+leftNum+1,p_end,mid+1,i_end)
return node
}
return helper(0,preorder.length-1,0,inorder.length-1)
};