解題:
//樹節(jié)點
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var buildTree = function(preorder, inorder) {
//獲取兩種遍歷數(shù)組長度
let preLen = preorder.length;
let inLen = inorder.length;
//如果長度不對那么有問題返回null
if(preLen != inLen) return null;
//將中序數(shù)組存儲到hash表,便于后面利用前序的根節(jié)點找中序的根節(jié)點下標(biāo)
let map = {};
for(let i = 0;i < inLen;i++) {
//數(shù)據(jù)作為鍵,下標(biāo)作為值
map[inorder[i]] = i;
}
//遞歸入口,傳入初始值
return recursionTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1, map);
}
/**
* 構(gòu)建下一個節(jié)點
*
* @param {*} preorder 前序遍歷
* @param {*} preLeft 前序遍歷左邊界(包括根)
* @param {*} preRight 前序遍歷右邊界
* @param {*} inorder 中序遍歷
* @param {*} inLeft 中序遍歷左邊界
* @param {*} inRight 中序遍歷右邊界
* @param {*} map 中序遍歷哈希表
*/
var recursionTree = function(preorder,preLeft,preRight,inorder,inLeft,inRight,map) {
//遞歸出口
if(preLeft > preRight || inLeft > inRight) return null;
//求中序遍歷的根inRootIndex => 從前序遍歷得到根,到哈希表得到中序遍歷該根的下標(biāo)
let inRootIndex = map[preorder[preLeft]];
//求左右子樹 => 中序遍歷inRootIndex下標(biāo)左邊是左子樹,右邊是右子樹
//根據(jù)左子樹長度求前序遍歷左子樹右邊界x(是個下標(biāo))
//x - preLeft - 1 = inRootIndex - 1 - inLeft
let x = inRootIndex + preLeft - inLeft;
//創(chuàng)建新節(jié)點
let TreeNode = {};
//新結(jié)點的值就是前序遍歷的根
TreeNode.val = preorder[preLeft];
//遞歸建立新節(jié)點的左子樹,這里傳的值是左子樹的前序遍歷和中序遍歷的邊界
TreeNode.left = recursionTree(preorder,preLeft + 1,x,inorder,inLeft,inRootIndex - 1,map);
//遞歸建立新節(jié)點的右子樹,這里傳的值是右子樹的前序遍歷和中序遍歷的邊界
TreeNode.right = recursionTree(preorder,x + 1,preRight,inorder,inRootIndex + 1,inRight,map);
return TreeNode;
}
