劍指Offer面試題：09 重建二叉樹

演算法不是金庸武俠小說里硬核的”九陽真經“，也不是輕量的”凌波微步“，它是程式員的基本功，如同練武之人需要扎馬步一般，功夫好不好，看看馬步扎不扎實；編程能力強不強，看看演算法能力有沒有，本系列采用leetcode題號，使用JavaScript為編程語言，本篇文章都會逐步分析解題思路，最終給出代碼，文章一方面是記錄筆者在刷題中的思路，已備學而時習之，另一方面也希望能跟大牛們多交流，有更高效的解法，或者文章有什么問題，望不吝賜教，

一、題目：重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，

例如，給出

前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]

回傳如下的二叉樹：

二、小馬甲思路

其實這道題的關鍵在于了解前序、中序遍歷是什么，了解它們的遍歷特點，才能更進一步的分析，現在我們已知二叉樹的前序遍歷為[3,9,20,15,7]，那能得出什么結論呢？對于前序遍歷來說，根節點必是陣列中第一個元素，

已知二叉樹的中序遍歷為[9,3,15,20,7]，由前序遍歷知道3對應根節點，而對于中序遍歷來說，根節點一定位于中間位置，即根節點左為左子樹，根節點右為右子樹，

根據中序遍歷的圖我們再來看，整個陣列代表一棵樹，根節點的左邊是一棵樹，根節點右邊也是一棵樹，這就把大樹分成了小樹，對小樹進行相同的拆分，直到只剩一個節點，每次處理一棵樹，我們都生成一個根節點，并將其左右樹遞回進行處理，并賦給根節點的left和right屬性，

總結一下有四步：

1. 首先，根據前序遍歷獲取并生成根節點
2. 其次，根據中序遍歷獲取中序左子樹和中序右子樹
3. 再次，對左子樹和右子樹遞回地執行1和2步驟，直到子樹數量為1，則直接回傳該節點
4. 最后，將生成的子樹添加至最初的根節點上

三、小馬甲題解

我們知道前序遍歷的第一個元素必對應根節點，因此也很容易生成根節點，

function TreeNode(key){
	this.key = key;
	this.left = this.right = null;
}

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	let root = new TreeNode(preorder[0]);
}

我們已知根節點值，就能獲取它在中序遍歷陣列中的位置inRootPos，根節點左邊即中序左子樹，根節點右邊即為中序右子樹，我們也能獲取前序左子樹，前序右子樹，

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	//let root = new TreeNode(preorder[0]);
	let inRootPos = inorder.indexOf(root);
	// 左子樹前序序列
	let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子樹中序序列 
	let inorderLeft = inorder.slice(0, inRootPos);
	// 右子樹前序序列 
	let preorderRight = preorder.slice(inRootPos + 1);
	// 右子樹中序序列
	let inorderRight = inorder.slice(inRootPos + 1);
}

現在我們擁有了左右子樹的前中遍歷序列，可以遞回地處理左右子樹，并把它設定為根節點的左右子樹，

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	//let root = new TreeNode(preorder[0]);
	//let inRootPos = inorder.indexOf(root);
	// 左子樹前序序列
	//let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子樹中序序列 
	//let inorderLeft = inorder.slice(0, inRootPos);
	// 右子樹前序序列 
	//let preorderRight = preorder.slice(inRootPos + 1);
	// 右子樹中序序列
	//let inorderRight = inorder.slice(inRootPos + 1);

	root.left = buildTree(preorderLeft, inorderLeft);
	root.right = buildTree(preorderRight, inorderRight);

	return root;
}

這個是我們的最終代碼，

function TreeNode(key){
	this.key = key;
	this.left = this.right = null;
}

function buildTree(preorder, inorder){
	if(preorder.length === 0){
		return null;
	}
	if(preorder.length === 1){
		return new Node(preorder[0]);
	}

	let root = new TreeNode(preorder[0]);
	let inRootPos = inorder.indexOf(root);
	// 左子樹前序序列
	let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子樹中序序列 
	let inorderLeft = inorder.slice(0, inRootPos);
	// 右子樹前序序列 
	let preorderRight = preorder.slice(inRootPos + 1);
	// 右子樹中序序列
	let inorderRight = inorder.slice(inRootPos + 1);

	root.left = buildTree(preorderLeft, inorderLeft);
	root.right = buildTree(preorderRight, inorderRight);

	return root;
}

四、總結

本文先從分析二叉樹的前序遍歷、中序遍歷入手，給出了四步的解題思路，再將思路逐步用代碼實作，把大問題拆小，遞回地處理左右子樹，最終得到了JavaScript版的演算法程式，

基礎知識關鍵字：二叉樹、樹的遍歷、遞回