解决1.二叉树先序中序后序遍历用递归和迭代如何实现？2.链表，二叉树这种数据结构嵌套定义看不懂
摘要：本文详细介绍了二叉树的三种遍历方式（先序、中序、后序）的递归和迭代实现方法。递归实现通过函数调用栈完成，代码简洁；迭代实现需手动使用栈模拟递归过程。其中先序遍历顺序为根→左→右，中序为左→根→右，后序为左→右→根。后序遍历的迭代实现可通过先序遍历的变种（根→右→左）后再反转结果列表来简化操作。每种遍历方式都给出了Java代码示例。
1.二叉树先序中序后序遍历用递归和迭代如何实现？
二叉树的先序、中序、后序遍历是树结构的基础操作，递归实现简洁直观（利用函数调用栈），迭代实现需手动模拟栈操作。以下是具体实现及思路解析：
基础定义（二叉树节点）
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
一、先序遍历（根 → 左 → 右）
1. 递归实现
核心思路：先访问当前节点，再递归左子树，最后递归右子树。
import java.util.ArrayList;
import java.util.List;
public class PreorderTraversal {
// 递归实现先序遍历
public List<Integer> preorderRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderHelper(root, result);
return result;
}
private void preorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return; // 空节点直接返回
result.add(node.val); // 1. 访问根节点
preorderHelper(node.left, result); // 2. 递归左子树
preorderHelper(node.right, result); // 3. 递归右子树
}
}
2. 迭代实现（手动用栈模拟）
核心思路：
- 用栈存储待访问节点，先将根节点入栈；
- 弹出节点时访问它，再按 “右子树 → 左子树” 的顺序入栈（因栈是 LIFO，左子树会先被弹出访问）。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PreorderTraversal {
// 迭代实现先序遍历
public List<Integer> preorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root); // 根节点入栈
while (!stack.isEmpty()) {
TreeNode node = stack.pop(); // 弹出栈顶节点
result.add(node.val); // 访问当前节点
// 右子树先入栈（后访问），左子树后入栈（先访问）
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}
}
二、中序遍历（左 → 根 → 右）
1. 递归实现
核心思路：先递归左子树，再访问当前节点，最后递归右子树。
import java.util.ArrayList;
import java.util.List;
public class InorderTraversal {
// 递归实现中序遍历
public List<Integer> inorderRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
inorderHelper(node.left, result); // 1. 递归左子树
result.add(node.val); // 2. 访问根节点
inorderHelper(node.right, result); // 3. 递归右子树
}
}
2. 迭代实现（手动用栈模拟）
核心思路：
- 先遍历到最左节点，过程中所有节点入栈；
- 当左子树为空时，弹出栈顶节点（左子树已遍历完），访问它，再转向右子树重复流程。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InorderTraversal {
// 迭代实现中序遍历
public List<Integer> inorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
// 1. 遍历到最左节点，所有节点入栈
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 2. 左子树为空，弹出栈顶节点（根）并访问
cur = stack.pop();
result.add(cur.val);
// 3. 转向右子树
cur = cur.right;
}
return result;
}
}
三、后序遍历（左 → 右 → 根）
1. 递归实现
核心思路：先递归左子树，再递归右子树，最后访问当前节点。
import java.util.ArrayList;
import java.util.List;
public class PostorderTraversal {
// 递归实现后序遍历
public List<Integer> postorderRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
postorderHelper(node.left, result); // 1. 递归左子树
postorderHelper(node.right, result); // 2. 递归右子树
result.add(node.val); // 3. 访问根节点
}
}
2. 迭代实现（手动用栈模拟）
1.核心思路：后序遍历是 “左→右→根”，可通过先序遍历的变种（根→右→左）再反转结果实现（更简洁）：
- 先按 “根→右→左” 顺序遍历（类似先序，调整左右入栈顺序）；
- 最后反转结果列表，得到 “左→右→根”。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class PostorderTraversal {
// 迭代实现后序遍历（基于先序变种反转）
public List<Integer> postorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val); // 先按“根→右→左”收集
// 左子树先入栈（后访问），右子树后入栈（先访问）
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
// 反转结果，得到“左→右→根”
Collections.reverse(result);
return result;
}
}
方法二：
后序遍历的直接迭代实现（不反转）核心在于通过栈跟踪节点状态，确保 “左子树→右子树→根节点” 的访问顺序。关键是需要判断：当前节点的左右子树是否已经被访问过，只有当左右子树都访问完毕后，才能访问当前节点。
直接迭代实现（不反转）的核心思路
- 用栈存储待处理节点，同时用一个指针
prev记录上一次访问的节点（用于判断子树是否已访问）。 - 对于栈顶节点，分三种情况处理：
- 若左右子树都为空：直接访问当前节点（叶子节点）。
- 若右子树已访问（
prev是右子节点）：说明左子树也已访问（因左子树优先处理），可访问当前节点。 - 若左子树已访问且右子树为空（
prev是左子节点）：可访问当前节点。
- 若不满足上述条件，则按 “右子树→左子树” 的顺序入栈（栈是 LIFO，确保左子树先被处理）。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PostorderTraversal {
// 直接迭代实现后序遍历（不反转，左→右→根）
public List<Integer> postorderIterativeDirect(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null; // 记录上一次访问的节点
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.peek(); // 查看栈顶节点（不弹出）
// 情况1：当前节点是叶子节点（左右都为空），直接访问
// 情况2：右子树已访问（prev是右子节点），说明左子树也已访问，可访问当前节点
// 情况3：左子树已访问且右子树为空（prev是左子节点），可访问当前节点
if ((curr.left == null && curr.right == null) ||
(prev != null && curr.right == prev) ||
(prev != null && curr.left == prev && curr.right == null)) {
stack.pop(); // 弹出栈顶节点
result.add(curr.val); // 访问当前节点
prev = curr; // 更新上一次访问的节点
} else {
// 先压右子树（后处理），再压左子树（先处理）
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}
return result;
}
}
代码执行流程示例（以树 [1,2,3,4,5,null,6] 为例）
1
/ \
2 3
/ \ \
4 5 6
后序遍历预期结果：[4,5,2,6,3,1]
步骤拆解：
- 初始栈：
[1]，prev=null。 curr=1，左右子树非空且prev无匹配，压入右（3）、左（2）→ 栈：[1,3,2]。curr=2，左右子树非空且prev无匹配，压入右（5）、左（4）→ 栈：[1,3,2,5,4]。curr=4，左右为空 → 弹出访问，result=[4]，prev=4→ 栈：[1,3,2,5]。curr=5，左右为空 → 弹出访问，result=[4,5]，prev=5→ 栈：[1,3,2]。curr=2，prev=5（右子节点）→ 弹出访问，result=[4,5,2]，prev=2→ 栈：[1,3]。curr=3，右子树非空且prev无匹配，压入右（6）→ 栈：[1,3,6]。curr=6，左右为空 → 弹出访问，result=[4,5,2,6]，prev=6→ 栈：[1,3]。curr=3，prev=6（右子节点）→ 弹出访问，result=[4,5,2,6,3]，prev=3→ 栈：[1]。curr=1，prev=3（右子节点）→ 弹出访问，result=[4,5,2,6,3,1]，循环结束。
关键逻辑解析
prev指针的作用：通过记录上一次访问的节点，判断当前节点的子树是否已处理完毕（尤其是右子树，因为后序遍历中右子树处理完才能处理根）。- 入栈顺序：先右后左，确保左子树先被弹出处理（满足 “左→右” 的顺序）。
- 访问条件：严格判断 “左右子树均已处理”，避免提前访问根节点。
这种方式无需反转结果，直接按后序顺序收集节点，逻辑更贴合后序遍历的本质，但实现稍复杂于 “先序变种 + 反转” 的方式。
总结：递归与迭代的对比
| 遍历方式 | 递归实现 | 迭代实现 | 核心差异 |
|---|---|---|---|
| 先序 | 根→左→右，直接递归 | 栈存储节点，弹出时访问根，先右后左入栈 | 迭代用栈模拟递归调用顺序 |
| 中序 | 左→根→右，左递归完访问根 | 栈存储左路径，弹出时访问根，转向右子树 | 迭代需先遍历到最左节点 |
| 后序 | 左→右→根，左右递归完访问根 | 基于先序变种（根→右→左）反转结果 | 后序顺序可通过先序调整反转得到 |
本质联系：递归的底层依赖函数调用栈，迭代则手动用栈模拟这一过程，核心都是通过栈管理节点访问顺序。
2.链表，二叉树这种数据结构嵌套定义看不懂
链表和二叉树的 “嵌套定义” 看起来复杂，本质是因为它们用 “自己定义自己” 的方式描述节点间的关系，但只要抓住 “节点是基本单元，指针是连接工具” 的核心，就很容易理解。我们一步步拆解：
一、先搞懂 “节点”：数据结构的最小单元
无论是链表还是二叉树，都是由 “节点”（Node） 组成的，节点就像一个 “数据盒子”，里面装两样东西：
- 实际存储的数据（比如整数、字符串）；
- 指向其他节点的 “指针”（或叫 “引用”，用来表示节点间的关系）。
“嵌套定义” 的关键：指针的类型和当前节点的类型相同（比如链表节点的next指针还是链表节点类型），因为指针要指向 “和自己一样的节点”。
二、链表的嵌套定义：“一条链” 的逻辑
链表的每个节点只需要知道 “下一个节点是谁”，所以结构很简单：
// 链表节点的定义
class ListNode {
int val; // 存储的数据（比如整数）
ListNode next; // 指向“下一个链表节点”的指针
// 构造方法
ListNode(int val) {
this.val = val;
this.next = null; // 初始时没有下一个节点
}
}
为什么是 “嵌套”？
ListNode类里有一个next变量，而next的类型又是ListNode—— 这就是 “自己定义自己”。但这不是 “无限套娃”，因为：
next只是一个指针（引用），它不 “包含” 另一个完整节点，只 “指向” 另一个节点的位置（类似地址）；- 实际使用时，节点是一个个单独创建的，通过
next指针串联起来，形成一条链：
// 创建3个节点
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
// 串联成链表：1 → 2 → 3
node1.next = node2; // node1的next指针指向node2
node2.next = node3; // node2的next指针指向node3
node3.next = null; // 最后一个节点的next为null（链结束）
图示理解：每个节点是一个 “小盒子”，next是盒子上的 “钩子”，用来勾住下一个盒子，形成一条直线：
[1 | 钩子] → [2 | 钩子] → [3 | 钩子] → null
三、二叉树的嵌套定义：“分岔路” 的逻辑
二叉树的每个节点需要知道 “左孩子” 和 “右孩子” 是谁（类似分岔路），所以结构里有两个指针：
// 二叉树节点的定义
class TreeNode {
int val; // 存储的数据
TreeNode left; // 指向“左孩子节点”的指针
TreeNode right; // 指向“右孩子节点”的指针
// 构造方法
TreeNode(int val) {
this.val = val;
this.left = null; // 初始时没有左孩子
this.right = null; // 初始时没有右孩子
}
}
为什么是 “嵌套”？
TreeNode类里的left和right变量，类型还是TreeNode—— 同样是 “自己定义自己”，但逻辑和链表类似：
left和right是 “指针”，只指向其他节点，不包含完整节点；- 实际使用时，节点通过
left和right分岔连接，形成树状结构：
// 创建3个节点
TreeNode root = new TreeNode(1);
TreeNode leftChild = new TreeNode(2);
TreeNode rightChild = new TreeNode(3);
// 构建二叉树：根节点1的左孩子是2，右孩子是3
root.left = leftChild; // 根节点的左指针指向leftChild
root.right = rightChild; // 根节点的右指针指向rightChild
图示理解：每个节点是一个 “小盒子”，有两个 “钩子”（左、右），可以勾住两个子节点，形成分岔：
plaintext
[1]
/ \
[2 | 左钩|右钩] [3 | 左钩|右钩]
/ \ / \
null null null null
四、为什么 “嵌套定义” 能成立？
核心是 “指针是引用，不是实体”：
- 节点类的定义里，
next/left/right只是 “声明了一个指向同类节点的引用”，就像 “在盒子上画一个钩子的位置”，但钩子上暂时可以不挂东西（初始为null）； - 当我们创建具体节点后，再通过赋值让指针指向其他节点（“把钩子挂上另一个盒子”），这时候才形成实际的连接。
这就像 “快递单”：单子上有 “下一站地址”（类似指针），地址的格式和当前单子的格式一样（都是地址），但这不代表单子里包含下一个快递，只是记录了下一个的位置。
五、总结：抓住两个核心
- 节点是 “数据 + 指针” 的基本单元：每个节点独立存在，存储数据并通过指针找其他节点；
- 指针是 “连接工具”：指针的类型和节点类型相同，只是为了指向同类节点，不存在 “无限包含”，而是 “逻辑串联 / 分岔”。
理解了这两点，再看链表和二叉树的定义，就会发现它们其实是在描述 “如何用节点和指针构建出灵活的结构”—— 链表用一个指针连成 “线”，二叉树用两个指针分出 “叉”，仅此而已。
private class TrieNode {
Map<Character, TrieNode> children; // 哈希表存储子节点
boolean isEnd;
public TrieNode() {
children = new HashMap<>();
isEnd = false;
}
}
// Trie节点结构
private class TrieNode {
TrieNode[] children; // 子节点数组（存储26个字母）
boolean isEnd; // 标记是否为字符串结尾
public TrieNode() {
children = new TrieNode[26]; // 26个小写字母
isEnd = false;
}
}
这两种TrieNode的定义，核心差异在于子节点的存储方式：一个用固定大小的数组，一个用哈希表（HashMap）。它们本质上都是为了存储 “当前节点的后续字符对应的子节点”，但在空间效率、时间效率和适用场景上有显著区别。
一、先明确共性：都是 “子节点的容器”
无论用数组还是哈希表，children的核心作用是建立 “字符→子节点” 的映射—— 即：“当前节点后接某个字符时，应该指向哪个子节点”。isEnd的作用不变，始终标记 “当前节点是否是某个完整字符串的结尾”。
二、差异对比：数组 vs 哈希表
1. 数组实现（TrieNode[] children）
children = new TrieNode[26]; // 固定长度26，对应26个小写英文字母
-
映射逻辑：通过字符的 ASCII 码计算索引（如
'a'→0，'b'→1，…，'z'→25），直接访问数组下标获取子节点。 -
优点
：
- 访问速度快：数组通过索引访问，时间复杂度是 O(1)（无需计算哈希，无冲突）。
- 实现简单：无需处理哈希冲突，逻辑直接。
-
缺点
：
- 空间固定浪费：无论当前节点有多少个子节点（哪怕只有 1 个），都要占用 26 个
TrieNode的空间（如果字符集更大，比如包含大写字母、数字，数组长度会更大，浪费更严重）。 - 字符集受限：只适合固定且范围小的字符集（如仅 26 个小写字母），无法灵活支持多字符集（如中文、符号等）。
- 空间固定浪费：无论当前节点有多少个子节点（哪怕只有 1 个），都要占用 26 个
2. 哈希表实现（Map<Character, TrieNode> children）
children = new HashMap<>(); // 动态存储，键是字符，值是子节点
- 映射逻辑：直接以字符为键，子节点为值存入哈希表，通过
get(character)获取子节点。 - 优点：
- 空间灵活：用多少存多少（比如当前节点只有 3 个子节点，哈希表就只存 3 个键值对），不浪费空间。
- 支持任意字符集：无论字符是字母、数字、中文、符号，只要能作为 HashMap 的键（实现了
hashCode和equals），都能支持。
- 缺点：
- 访问速度略慢：哈希表访问需要计算字符的哈希值，可能存在哈希冲突，平均时间复杂度是 O(1)，但实际效率略低于数组。
- 实现稍复杂：需要依赖哈希表的底层逻辑（如自动扩容、冲突处理）。
三、用例子理解：两种方式如何存储 “apple” 和 “apply”
假设存储两个单词：apple（苹果）和apply（应用），两种实现的子节点存储差异如下：
数组实现：
每个节点的children是长度 26 的数组，只有用到的下标有值，其余为null：
根节点
└── children['a'-'a'] → 节点A（对应'a'）
└── children['p'-'a'] → 节点B（对应'p'）
└── children['p'-'a'] → 节点C（对应'p'）
└── children['l'-'a'] → 节点D（对应'l'）
├── children['e'-'a'] → 节点E（对应'e'，isEnd=true，"apple"结束）
└── children['y'-'a'] → 节点F（对应'y'，isEnd=true，"apply"结束）
// 数组其他24个下标（如0,1,2...）均为null
哈希表实现：
每个节点的children只存储实际用到的字符，键是字符本身：
根节点
└── children.get('a') → 节点A（对应'a'）
└── children.get('p') → 节点B（对应'p'）
└── children.get('p') → 节点C（对应'p'）
└── children.get('l') → 节点D（对应'l'）
├── children.get('e') → 节点E（对应'e'，isEnd=true，"apple"结束）
└── children.get('y') → 节点F（对应'y'，isEnd=true，"apply"结束）
// 哈希表中只有这两个键，无其他冗余数据
四、适用场景选择
-
用数组：当字符集固定且范围小时（如仅 26 个小写字母、10 个数字），优先选数组 —— 追求访问速度，容忍少量空间浪费。
例：实现一个英语词典的前缀查询功能。
-
用哈希表：当字符集不固定或范围大时（如包含大小写字母、中文、符号等），优先选哈希表 —— 追求空间灵活，接受轻微的时间损耗。
例：实现一个支持中英文混合的搜索提示功能。
总结
两种实现的核心是 “子节点映射方式” 的选择：
- 数组是 “以空间换时间”，适合小而固定的字符集；
- 哈希表是 “以时间换空间”，适合灵活或大的字符集。
它们都能正确实现字典树的功能，只是在性能和适用场景上各有侧重。
转载自CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/xxxxxxllllllshi/article/details/152013049
