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

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

思路分析

对于这类题我们还是思考二叉树的解题步骤：

• 能够遍历解决
• 能否递归解决
• 每个节点需要做什么

解题步骤

1. 对于前序遍历，我们可以很容易的发现根节点，根节点也就是第一个元素。
2. 之后通过中序遍历找到其中的根节点，那么再根节点左侧的也就是它的左子树，右侧的则就是右子树。
3. 获取左子树的长度，也就在中序遍历中索引从0开始一直到root的长度，我们可以通过indexOf来获取长度，索引即位长度。
4. 之后在先序遍历的结果中截取出左子树和右子树，左子树的第一个元素即为root元素。
5. 同样的，右子树也是通过先序遍历得到的，那同样也可以获取右子树的root
6. 之后通过递归完成，退出条件则是其中任意一个数组的长度为0

参考代码

var buildTree = function(preorder, inorder) {
	if (preorder.length === 0) return null;
	let tmp = preorder[0];
	let sz = inorder.indexOf(tmp); //通过索引来获取左侧部分的长度
	let root = new TreeNode(tmp);
	root.left = buildTree(preorder.slice(1, sz + 1), inorder.slice(0, sz));
	root.right = buildTree(preorder.slice(sz + 1), inorder.slice(sz + 1));
	return root;
};