在二叉树的问题中，给定二叉树的前序遍历（Preorder）和中序遍历（Inorder）序列，如何求得其后序遍历（Postorder）序列是一个经典的面试题。本文将详细介绍如何通过Java实现这一过程。
问题描述
前序遍历（Preorder）：按根节点 -> 左子树 -> 右子树的顺序访问节点。
中序遍历（Inorder）：按左子树 -> 根节点 -> 右子树的顺序访问节点。
后序遍历（Postorder）：按左子树 -> 右子树 -> 根节点的顺序访问节点。
给定前序遍历和中序遍历序列，我们需要构建二叉树并输出其后序遍历序列。
实现思路
- 重建二叉树：利用前序遍历和中序遍历的特性，通过递归方法重建二叉树。
- 后序遍历二叉树：通过递归方法进行后序遍历并输出结果。
实现步骤
1. 重建二叉树
首先，我们通过前序遍历的第一个元素确定根节点。在中序遍历中找到该根节点的位置，可以将中序遍历数组分为左子树和右子树两部分。递归地对这两部分继续构建左右子树。
2. 后序遍历
在构建好的二叉树上进行后序遍历，按左子树 -> 右子树 -> 根节点的顺序输出节点值。
代码实现
以下是完整的Java实现代码：
import java.util.HashMap; import java.util.Map; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class BinaryTree { private int preIndex = 0; private Map<Integer, Integer> inorderIndexMap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { inorderIndexMap.put(inorder[i], i); } return buildTreeHelper(preorder, 0, inorder.length - 1); } private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) { if (inorderStart > inorderEnd) { return null; } int rootVal = preorder[preIndex++]; TreeNode root = new TreeNode(rootVal); int inorderIndex = inorderIndexMap.get(rootVal); root.left = buildTreeHelper(preorder, inorderStart, inorderIndex - 1); root.right = buildTreeHelper(preorder, inorderIndex + 1, inorderEnd); return root; } 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 = {3, 9, 20, 15, 7}; int[] inorder = {9, 3, 15, 20, 7}; BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.buildTree(preorder, inorder); System.out.println("Postorder traversal:"); binaryTree.postorderTraversal(root); } }
代码解释
- TreeNode类：定义二叉树节点的数据结构。
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
BinaryTree类：包含重建二叉树和后序遍历的方法。
buildTree方法：接受前序遍历和中序遍历数组，构建并返回二叉树的根节点。buildTreeHelper方法：递归地构建二叉树。
postorderTraversal方法：递归地进行后序遍历，并输出节点值。
- buildTreeHelper方法：通过前序遍历的当前节点值和中序遍历的索引，递归地构建左右子树。
private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) { if (inorderStart > inorderEnd) { return null; // Base case: no elements to construct the tree } int rootVal = preorder[preIndex++]; // Get the current root value from preorder traversal TreeNode root = new TreeNode(rootVal); // Create the root node int inorderIndex = inorderIndexMap.get(rootVal); // Find the index of the root in inorder traversal // Recursively build the left subtree root.left = buildTreeHelper(preorder, inorderStart, inorderIndex - 1); // Recursively build the right subtree root.right = buildTreeHelper(preorder, inorderIndex + 1, inorderEnd); return root; }
后序遍历：通过递归方法进行后序遍历，按照左子树 -> 右子树 -> 根节点的顺序输出节点值。
public void postorderTraversal(TreeNode root) { if (root == null) { return; } postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.val + " "); }
main方法：创建前序遍历和中序遍历数组，调用buildTree方法构建二叉树，然后调用postorderTraversal方法输出后序遍历结果。
public static void main(String[] args) { int[] preorder = {3, 9, 20, 15, 7}; int[] inorder = {9, 3, 15, 20, 7}; BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.buildTree(preorder, inorder); System.out.println("Postorder traversal:"); binaryTree.postorderTraversal(root); }
总结
通过上述步骤，我们可以实现根据前序遍历和中序遍历序列重建二叉树，并输出其后序遍历序列。这不仅帮助我们加深对二叉树遍历的理解，也为处理相关面试题提供了一个有力的工具。希望这篇文章对你有所帮助！
