给定一个二叉树的前序遍历和中序遍历结果,如何编写程序来推导后序遍历的结果?请提供示例代码。
时间: 2024-12-03 21:28:00 浏览: 2
当你面对一个编程问题,要求通过给定的前序遍历和中序遍历来推导后序遍历的结果时,你可以参考《全国计算机等级考试二级Java真题及答案解析》中的相关例题和解答,它将帮助你理解二叉树遍历的概念和解决方案。首先,要了解前序遍历是根节点-左子树-右子树的顺序,而中序遍历是左子树-根节点-右子树的顺序。后序遍历则是左子树-右子树-根节点的顺序。利用这一特性,你可以编写程序来递归地构建二叉树,并通过遍历得到后序遍历的结果。以下是一个简单的示例代码:
参考资源链接:[全国计算机等级考试二级Java真题及答案解析](https://wenku.csdn.net/doc/22v0twti7o?spm=1055.2569.3001.10343)
```java
public class BinaryTreePostOrder {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static int[] postorderTraversal(TreeNode root) {
if (root == null) return new int[0];
int[] left = postorderTraversal(root.left);
int[] right = postorderTraversal(root.right);
int[] result = new int[left.length + right.length + 1];
int index = 0;
for (int l : left) result[index++] = l;
for (int r : right) result[index++] = r;
result[index++] = root.val;
return result;
}
public static TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private static TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inRoot = inStart;
while (inorder[inRoot] != root.val) inRoot++;
int leftTreeSize = inRoot - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, inRoot - 1);
root.right = buildTree(preorder, preStart + leftTreeSize + 1, preEnd, inorder, inRoot + 1, inEnd);
return root;
}
public static void main(String[] args) {
int[] preorder = {3,9,20,15,7};
int[] inorder = {9,3,15,20,7};
TreeNode root = buildTree(preorder, inorder);
int[] postorder = postorderTraversal(root);
for (int value : postorder) {
System.out.print(value +
参考资源链接:[全国计算机等级考试二级Java真题及答案解析](https://wenku.csdn.net/doc/22v0twti7o?spm=1055.2569.3001.10343)
阅读全文