題目描述
輸入某二叉樹的前序周遊和中序周遊的結果,請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6},則重建二叉樹并傳回。
思路:
二叉樹的先序周遊中,第一個數字是根節點的值。通過根節點的值,能夠将中序周遊劃分為左子樹和右子樹兩個部分。然後遞歸左子樹和右子樹。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
if(pre.length == 0 || in.length == 0) {
return null;
}
return core(pre, 0, pre.length-1, in, 0, in.length-1);
}
public TreeNode core(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
for(int i = inStart; i <= inEnd; i++) {
if(in[i] == pre[preStart]) {
root.left = core(pre, preStart + 1, preStart + i - inStart, in, inStart, i - 1);
root.right = core(pre, preStart + i -inStart + 1, preEnd, in, i + 1, inEnd);
break;
}
}
return root;
}
}
寫法2:
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0) {
return null;
}
return reConstruct(pre, 0, pre.length - 1,
in, 0, in.length - 1);
}
public TreeNode reConstruct(int[] pre, int preStart, int preEnd,
int[] in, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode node = new TreeNode(pre[preStart]);
int headIndex = getIndex(in, node.val);
node.left = reConstruct(pre, preStart + 1, preStart + (headIndex - inStart),
in, inStart, headIndex - 1);
node.right = reConstruct(pre, preStart + 1 + (headIndex - inStart), preEnd,
in, headIndex + 1, inEnd);
return node;
}
public int getIndex(int[] in, int target) {
for (int i = 0; i < in.length; i++) {
if (in[i] == target) {
return i;
}
}
return 0;
}