使用 JavaScript 解答 LeetCode 第 105 题,从前序与中序遍历序列构造二叉树,中等难度。
原题
原题链接
本题是 LeetCode 题库第 105 题,由此访问。
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
解题
AC 样例
/**
* 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 || inorder.length < 1) return null;
const index = preorder.shift();
const node = new TreeNode(index);
const n = inorder.indexOf(index);
const leftTree = inorder.slice(0, n);
const rightTree = inorder.slice(n+1);
node.left = buildTree(preorder, leftTree);
node.right = buildTree(preorder, rightTree);
return node;
};
解题思路
这个题目考察的内容非常基础,主要是二叉树的概念,树的遍历次序和规律。
根据前序遍历的规则,根节点位于遍历序列第一位,其后分别是左右子树。对应到中序遍历序列中,位于根节点左侧的数据即为具体的左子树节点,其右侧为具体的右子树节点。若子树节点有多个,则返回前序遍历序列中查找该子树的根节点,进一步缩小数据规模。
每一个子树均按照相同的规则构建,自上而下的构建完成后便得到符合要求的二叉树。