leetcode——重建二叉樹

【題目描述】：輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

【主要思路】：前序周遊是按照根節點、左節點、右節點的順序進行，中序周遊是按照左節點、根節點、右節點的順序進行周遊。

前序周遊序列中的第一個元素對應整個樹的根節點

rootNode

，在中序周遊序列中找到

rootNode所在位置rootIndex

，

rootIndex之前的所有元素為整個左子樹，rootIndex後面的所有元素是整個右子樹

；

同樣的，找到左子樹的跟節點和左子樹和右子樹，右子樹也是一樣。

利用遞歸的思想可以很容易實作，代碼如下：

function ListNode(x){
	this.val=x;
	this.left=null;
	this.right=null;
}

function reConstructBinartTree(pre,vin){
	function build(preStart,preEnd,vinStart,vinEnd){
		let rootNode=new ListNode(pre[preStart]);//根節點
		let rootIndex=vin.indexOf(pre[preStart]),//根節點下标
		leftLen=rootIndex-vinStart;//左子樹長度
		if(leftLen>0){ //如果左子樹長度大于0，則周遊左子樹
			rootNode.left=build(preStart+1,preStart+leftLen,vinStart,rootIndx-1)
		}
		if(leftLen<preEnd-preStart){ //存在右子樹,則周遊右子樹
			rootNode.right=build(preStart+leftLen+1,preEnd,rootIndex+1,vinEnd)
		}
		return rootNode
	}
	let head=build(0,pre.length-1,0,vin.length-1)
	return head
}