重建二叉樹
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果懦傍，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字赋秀。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}睬愤，則重建二叉樹并返回。
實(shí)現(xiàn)代碼
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
// write code here
if (!pre || pre.length === 0) {
return;
}
var treeNode = {
val: pre[0]
}
for(var i = 0; i < pre.length; i++) {
if (vin[i] === pre[0]) {
treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
}
}
return treeNode;
console.log(treeNode)
}
相關(guān)知識
二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)统锤。
前序遍歷：首先訪問根，再先序遍歷左子樹炭庙，最后先序遍歷右子樹饲窿。
中序遍歷：首先中序遍歷左子樹，再訪問根焕蹄，最后中序遍歷右子樹逾雄。
后序遍歷：首先后序遍歷左子樹，再后序遍歷右子樹腻脏，最后訪問根鸦泳。
思路
先序遍歷第一個位置是根節(jié)點(diǎn)treeNode，中序遍歷的根節(jié)點(diǎn)位置在中間p永品，在p左邊的肯定是treeNode的左子樹的中序數(shù)組做鹰，p右邊的肯定是treeNode的右子樹的中序數(shù)組； 另一方面鼎姐，先序遍歷的第二個位置到p钾麸，也是treeNode左子樹的先序子數(shù)組，剩下p右邊的就是treeeNode的右子樹的先序子數(shù)組炕桨，把四個數(shù)組找出來饭尝，分左右遞歸調(diào)用即可。
