Open
Description
习题
出处 LeetCode 算法第105题
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
思路
按照思路递归遍历数组，前序遍历的第一个值为树的根，其在中序遍历中对应的值的前面的数都在其左子树上
解答
/**
* 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}
*/
function helper(preorder, inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
var rootVal = preorder[0];
var index = inorder.indexOf(rootVal);
var perorderLeft = preorder.slice(1, index + 1);
var perorderRight = preorder.slice(index + 1);
var InorderLeft = inorder.slice(0, index);
var InorderRight = inorder.slice(index + 1);
var root = new TreeNode(rootVal);
if (perorderLeft.length > 0) {
root.left = buildTree(perorderLeft, InorderLeft);
}
if (perorderRight.length > 0) {
root.right = buildTree(perorderRight, InorderRight);
}
return root;
}
var buildTree = function (preorder, inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return [];
}
return helper(preorder, inorder);
};Metadata
Metadata
Assignees
Labels
No labels