在Java中,可以根據給定的前序遍歷和后序遍歷數組構建二叉樹。下面是一個示例代碼:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeBuilder {
public TreeNode buildTree(int[] preOrder, int[] postOrder) {
return buildTreeHelper(preOrder, postOrder, 0, preOrder.length - 1, 0, postOrder.length - 1);
}
private TreeNode buildTreeHelper(int[] preOrder, int[] postOrder, int preStart, int preEnd, int postStart, int postEnd) {
if (preStart > preEnd || postStart > postEnd) {
return null;
}
TreeNode root = new TreeNode(preOrder[preStart]);
if (preStart == preEnd) {
return root;
}
int leftRootVal = preOrder[preStart + 1];
int leftRootIndex = postStart;
while (postOrder[leftRootIndex] != leftRootVal) {
leftRootIndex++;
}
int leftTreeSize = leftRootIndex - postStart + 1;
root.left = buildTreeHelper(preOrder, postOrder, preStart + 1, preStart + leftTreeSize, postStart, leftRootIndex);
root.right = buildTreeHelper(preOrder, postOrder, preStart + leftTreeSize + 1, preEnd, leftRootIndex + 1, postEnd - 1);
return root;
}
}
在這段代碼中,我們首先定義了一個TreeNode
類表示二叉樹的節點。然后定義了一個BinaryTreeBuilder
類來構建二叉樹。在buildTree
方法中,我們調用buildTreeHelper
方法來遞歸構建二叉樹。在buildTreeHelper
方法中,我們首先創建根節點,并根據前序遍歷數組和后序遍歷數組的特點,找到左子樹的根節點值和左子樹的大小,然后遞歸構建左子樹和右子樹。
最后,我們可以調用buildTree
方法來構建二叉樹,并傳入前序遍歷數組和后序遍歷數組作為參數。