用java代码实现给出一颗二叉树的先序遍历序列和中序遍历序列,试着找出它的后序遍历序列。
时间: 2023-12-30 22:02:41 浏览: 24
以下是Java代码实现:
```
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeTraversal {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int index = findIndex(inorder, rootVal, inStart, inEnd);
int leftSize = index - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
private int findIndex(int[] arr, int target, int start, int end) {
for (int i = start; i <= end; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
public void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val + " ");
}
public static void main(String[] args) {
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 5, 1, 6, 3, 7};
BinaryTreeTraversal btt = new BinaryTreeTraversal();
TreeNode root = btt.buildTree(preorder, inorder);
System.out.print("后序遍历序列为: ");
btt.postorderTraversal(root);
}
}
```
输出结果为:后序遍历序列为: 4 5 2 6 7 3 1