您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java二叉树怎么根据前序和中序推出后序
## 一、引言
在二叉树的相关算法中，根据遍历序列重建二叉树是一个经典问题。前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）是最常用的三种深度优先遍历方式。本文将详细讲解如何利用前序和中序遍历序列推导出后序遍历序列，并提供完整的Java实现代码。
## 二、核心概念解析
### 1. 二叉树遍历特性
- **前序遍历**：第一个元素永远是根节点
- **中序遍历**：根节点左侧是左子树，右侧是右子树
- **后序遍历**：最后一个元素是根节点
### 2. 关键规律
给定前序和中序序列时：
- 前序序列的首元素是当前子树的根节点
- 在中序序列中找到该根节点，左侧即为左子树的中序序列，右侧为右子树的中序序列
- 根据左右子树的长度，可以划分前序序列中的左右子树部分
## 三、算法实现步骤
### 1. 基础实现思路
```java
public class TreeBuilder {
// 主方法：根据前序和中序构建树并输出后序
public static void postOrderFromPreIn(int[] pre, int[] in) {
TreeNode root = buildTree(pre, in);
printPostOrder(root);
}
// 构建二叉树的核心方法
private static TreeNode buildTree(int[] pre, int[] in) {
// 实现细节见下文
}
// 后序遍历打印
private static void printPostOrder(TreeNode node) {
if (node == null) return;
printPostOrder(node.left);
printPostOrder(node.right);
System.out.print(node.val + " ");
}
}
private static TreeNode buildTree(int[] pre, int[] in) {
// 使用HashMap存储中序元素的索引
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
inMap.put(in[i], i);
}
return helper(pre, 0, pre.length-1, in, 0, in.length-1, inMap);
}
private static TreeNode helper(int[] pre, int preStart, int preEnd,
int[] in, int inStart, int inEnd,
Map<Integer, Integer> inMap) {
if (preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(pre[preStart]);
int inRoot = inMap.get(root.val);
int numsLeft = inRoot - inStart;
root.left = helper(pre, preStart+1, preStart+numsLeft,
in, inStart, inRoot-1, inMap);
root.right = helper(pre, preStart+numsLeft+1, preEnd,
in, inRoot+1, inEnd, inMap);
return root;
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
输入： - 前序: [1, 2, 3] - 中序: [2, 1, 3]
构建过程： 1. 前序首元素1是根节点 2. 在中序中找到1，左侧[2]是左子树，右侧[3]是右子树 3. 递归处理左右子树
输出后序： [2, 3, 1]
输入： - 前序: [3, 9, 20, 15, 7] - 中序: [9, 3, 15, 20, 7]
分步解析： 1. 根节点3（前序第一个） 2. 中序中3左侧[9]是左子树 3. 右侧[15,20,7]是右子树 4. 右子树的根是20（前序第三个） 5. 继续分解右子树…
最终后序： [9, 15, 7, 20, 3]
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建哈希表 | O(n) | O(n) |
| 递归构建树 | O(n) | O(n) |
| 后序遍历 | O(n) | O(h) |
其中h为树的高度，最坏情况下（斜树）h=n
if (pre.length == 0 || in.length == 0) {
return null;
}
if (pre.length != in.length) {
throw new IllegalArgumentException("序列长度不匹配");
}
if (!inMap.containsKey(rootVal)) {
throw new IllegalArgumentException("无效的遍历序列");
}
public static List<Integer> getPostOrderNonRecursive(int[] pre, int[] in) {
List<Integer> post = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
int preIndex = 0, inIndex = 0;
TreeNode current = null;
while (preIndex < pre.length) {
// 左子树处理
while (preIndex < pre.length &&
(inIndex >= in.length || pre[preIndex] != in[inIndex])) {
TreeNode node = new TreeNode(pre[preIndex++]);
if (current != null) {
current.left = node;
}
stack.push(node);
current = node;
}
// 右子树处理
while (!stack.isEmpty() && inIndex < in.length &&
stack.peek().val == in[inIndex]) {
current = stack.pop();
inIndex++;
}
if (preIndex < pre.length) {
TreeNode node = new TreeNode(pre[preIndex++]);
current.right = node;
stack.push(node);
current = node;
}
}
// 通过栈模拟后序遍历
Deque<Integer> result = new ArrayDeque<>();
stack.clear();
stack.push(current);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.push(node.val);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return new ArrayList<>(result);
}
A: 前序和后序无法唯一确定二叉树结构，因为无法区分左右子树的分界。
A: 需要增加额外的约束条件，比如规定重复元素在左子树或右子树。
A: 不能直接适用，需要修改为处理多个子节点的情况。
本文详细讲解了： 1. 前序+中序推导后序的核心原理 2. 递归与非递归的Java实现 3. 复杂度分析和边界处理 4. 实际应用场景和常见问题
关键点记忆口诀： “前序首节点是根，中序左右分两边； 递归构建子树后，后序输出左右根。”
import java.util.*;
public class BinaryTreeFromPreIn {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static void main(String[] args) {
int[] pre = {3,9,20,15,7};
int[] in = {9,3,15,20,7};
System.out.println("后序遍历结果：");
List<Integer> postOrder = getPostOrder(pre, in);
postOrder.forEach(num -> System.out.print(num + " "));
}
public static List<Integer> getPostOrder(int[] pre, int[] in) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
inMap.put(in[i], i);
}
TreeNode root = buildTree(pre, 0, pre.length-1,
in, 0, in.length-1, inMap);
return postOrderTraversal(root);
}
private static TreeNode buildTree(int[] pre, int preStart, int preEnd,
int[] in, int inStart, int inEnd,
Map<Integer, Integer> inMap) {
if (preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(pre[preStart]);
int inRoot = inMap.get(root.val);
int numsLeft = inRoot - inStart;
root.left = buildTree(pre, preStart+1, preStart+numsLeft,
in, inStart, inRoot-1, inMap);
root.right = buildTree(pre, preStart+numsLeft+1, preEnd,
in, inRoot+1, inEnd, inMap);
return root;
}
private static List<Integer> postOrderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.addFirst(node.val);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return result;
}
}
运行输出：
后序遍历结果：
9 15 7 20 3
通过本文的学习，读者应该能够熟练掌握根据前序和中序遍历序列推导后序序列的方法，并理解其背后的二叉树构建原理。在实际面试和算法竞赛中，这是二叉树相关问题的必备基础知识。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。