1. 题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
2. 解题思路
对于这道题,我们先看下前序遍历和中序遍历的规律:
前序遍历的顺序是根节点、左子节点、右子节点,所以数组第一个值就是二叉树的根节点,然后我们看中序遍历,中序遍历的顺序是左子节点、根节点、右子节点,所以我们可以根据上面获得根据点判断,哪些是左子节点,哪些是右子节点,依次这样判断即可。
就拿上面的例子来说,我们从前序遍历数组中看出3是二叉树的根节点,然后在中序遍历数组中,我们可以知道3之前的都是左子节点,3之后的都是右子节点,3就是它们的中间值。我们在分别截出左右子节点的前序和中序遍历的数组,进行递归操作,就可以得到相应的二叉树。
3. 代码实现
/**
* 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 null
let tmp = preorder[0]
let mid = inorder.indexOf(tmp)
let root = new TreeNode(tmp)
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
};