描述
給定節點數為 n 的二叉樹的前序周遊和中序周遊結果，請重建出該二叉樹并傳回它的頭結點。
例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均無重複元素
3.vin出現的元素均出現在 pre裡
4.隻需要傳回根結點，系統會自動輸出整顆樹做答案對比
資料範圍：n ≤ 2000，節點的值 -10000 ≤ val ≤ 10000
要求：空間複雜度 O(n)，時間複雜度 O(n)
示例1
輸入：
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6] 傳回值：
{1,2,3,4,#,5,6,#,7,#,#,8}
示例2
輸入：
[1],[1] 傳回值：
{1} 複制
示例3
輸入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7] 傳回值：
{1,2,5,3,4,6,7} 說明：
傳回根節點，系統會輸出整顆二叉樹對比結果，重建結果如題面圖示
java建構的二叉樹
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
算法思想一：遞歸
解題思路：
二叉樹的前序周遊：根左右；中序周遊：左根右
由前序周遊知道根節點之後，能在中序周遊上劃分出左子樹和右子樹。分别對中序周遊的左右子樹遞歸進行這一過程即可建樹。
圖解：
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if(pre.length==0||vin.length==0)
return null;
TreeNode result = new TreeNode(pre[0]);
for(int i = 0;i<vin.length;i++)
{
if(vin[i]==pre[0]){
result.left = reConstructBinaryTree( Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(vin,0,i));
result.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
break;
}
}
return result;
}
}
算法思想二：指針
解題思路：
二叉樹的前序周遊：根左右；中序周遊：左根右
設定三個指針，一個是preStart，表示的是前序周遊開始的位置，一個是inStart，表示的是中序周遊開始的位置。一個是inEnd，表示的是中序周遊結束的位置，我們主要是對中序周遊的數組進行拆解
圖解：
前序序列：【1，2，3，4，5，6，7】
中序周遊：【3，2，4，1，6，5，7】
隻要找到了前序周遊的結點在中序周遊的位置，我們就可以把中序周遊數組分解為左右子樹兩部分。
1、中序序列的劃分
如果index是前序周遊的某個值在中序周遊數組中的索引，以index為根節點劃分，在中序周遊中，[0，index-1]就是根節點左子樹的所有節點，[index+1，tin.length-1]就是根節點右子樹的所有節點
2、前序序列的劃分
左子樹
對于前序序列，針對左子樹，preStart=index+1，如果是右子樹就稍微麻煩點，
右子樹
- 前序序列是 根->左->右
故，右子樹的位置就是從根節點開始走過左子樹，然後左子樹的下一個節點就是右子樹的第一個節點
公式表示：
- （根節點的位置）+（左子樹的數量）+1
- 根節點的位置=preStart
- 中序序列是 左->右->根
根據這個原理，左子樹的數量可以從中序周遊裡找，
即：找到中序周遊中根節點的位置，根節點的左邊有多少元素，左子樹就有幾個節點。
公式表示：
3. (index-inStart)
結合 2,3， 公式1表示為
preStart+ (index-inStart）+ 1
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return dfs(0, 0, in.length - 1, pre, in);
}
public TreeNode dfs(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
//建立結點
TreeNode root = new TreeNode(preorder[preStart]);
int index = 0;
//找到目前節點root在中序周遊中的位置，然後再把數組分兩半
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
index = i; break;
}
}
root.left = dfs(preStart + 1, inStart, index - 1, preorder, inorder);
root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder);
return root;
}
}
- 算法示意圖來自牛客，侵删，這兩篇有點深，對于初學者不太友好，至少得知道資料結構-樹，深度優先周遊等知識，沒看明白多看幾遍，也可以私信我！