Java 可以根據(jù)給定的前序遍歷和中序遍歷構(gòu)造二叉樹。首先，讓我們看看什么是前序遍歷和中序遍歷。

前序遍歷是將根節(jié)點(diǎn)排在子節(jié)點(diǎn)之前進(jìn)行遍歷的方式。其中，“根節(jié)點(diǎn)”是指一棵二叉樹的根，而“子節(jié)點(diǎn)”是指一個(gè)節(jié)點(diǎn)的左子樹或右子樹。因此，前序遍歷的順序?yàn)椋焊?jié)點(diǎn)，左子樹，右子樹。

1
 /   \
2     3
/ \
4   5

如上圖所示，如果以 1 為根，那么先訪問 1，再訪問 2，最后訪問 3、4、5。

中序遍歷是將根節(jié)點(diǎn)排在子節(jié)點(diǎn)之間進(jìn)行遍歷的方式，因此中序遍歷的順序?yàn)椋鹤笞訕洌?jié)點(diǎn)，右子樹。

4
 /   \
2     5
 \     
3

如上圖所示，如果以 4 為根，那么先訪問 2，再訪問 3，最后訪問 5。

現(xiàn)在回到 Java 中如何根據(jù)前序遍歷和中序遍歷構(gòu)造二叉樹。我們可以按照以下步驟進(jìn)行：

1. 從前序遍歷序列中取出根節(jié)點(diǎn)。

1
/ \

2. 在中序遍歷序列中找到根節(jié)點(diǎn)所在的位置。

4
/   \
2     5
\
3

3. 根據(jù)中序遍歷序列中根節(jié)點(diǎn)所在的位置，可以知道左子樹的節(jié)點(diǎn)個(gè)數(shù)和右子樹的節(jié)點(diǎn)個(gè)數(shù)。

1
/ \
/__\
/    \
[2  3] [4  5]

4. 根據(jù)左子樹和右子樹的節(jié)點(diǎn)個(gè)數(shù)，可以在前序遍歷序列中找到左子樹和右子樹的范圍。

[1] [2] [3] [4] [5]
先序：[1] [2] [3] [4] [5]
/   
中序：[2] [3] [4] [1] [5]
\
后序：[3] [2] [4] [5] [1]

5. 遞歸構(gòu)造左子樹和右子樹，然后返回根節(jié)點(diǎn)。

1
 /   \
2     3
/ \
4   5

以上就是根據(jù)前序遍歷和中序遍歷構(gòu)造二叉樹的過程。使用 Java 代碼實(shí)現(xiàn)時(shí)，可以使用遞歸函數(shù)來實(shí)現(xiàn)，在每一次遞歸返回時(shí)，返回當(dāng)前子樹的根節(jié)點(diǎn)即可。

public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return buildTreeSub(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeSub(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if(preStart >preEnd) {
return null;
}
int rootValue = preorder[preStart];
int rootIndex = inStart;
while(rootIndex<= inEnd && inorder[rootIndex] != rootValue) {
rootIndex++;
}
int leftSize = rootIndex - inStart;
TreeNode root = new TreeNode(rootValue);
root.left = buildTreeSub(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root.right = buildTreeSub(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}