行业知识
代码随想录算法训练营第十四天|144、94、145 二叉树的前序遍历、中序遍历、后序遍历（递归法和迭代法）
2026-11-02 06:03:31
来源：互联网转载
文章和视频讲解如下：
- ���章讲解（递归法）https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF
- 文章讲解（迭代法）https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html
- 视频讲解(递归法)https://www.bilibili.com/video/BV1Wh411S7xt/?vd_source=af4853e80f89e28094a5fe1e220d9062
- 视频讲解(迭代法)https://www.bilibili.com/video/BV15f4y1W7i2/?spm_id_from=333.788&vd_source=af4853e80f89e28094a5fe1e220d9062
144、二叉树的前序遍历
- 刷题https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
-
题解1（递归法）：
/** * Definition for a binary tree node. * 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; * } * } */class Solution { //先序遍历 public List preorderTraversal(TreeNode root) { List result = new ArrayList(); preorder(root,result); return result; } public void preorder(TreeNode root,List result){ if(root == null){ return; } result.add(root.val); preorder(root.left, result); preorder(root.right, result); }}-
题解2（迭代法）：
/** * Definition for a binary tree node. * 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; * } * } */class Solution { public List preorderTraversal(TreeNode root) { //存储结果 List result = new ArrayList(); //若传入树为空则直接返回空结果 if(root == null){ return result; } //辅助栈 Stack st = new Stack(); //推入根结点 st.push(root); //辅助栈非空，将当前栈中结点弹出同时推入当前结点的右孩子和左孩子（顺序不可变） while(!st.isEmpty()){ TreeNode cur = st.pop(); result.add(cur.val); if(cur.right != null){ st.push(cur.right); } if(cur.left != null){ st.push(cur.left); } } return result; }}94、二叉树的中序遍历
- 刷题https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
-
题解1（递归法）:
/** * Definition for a binary tree node. * 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; * } * } */class Solution { //中序遍历 public List inorderTraversal(TreeNode root) { List result = new ArrayList(); inorder(root, result); return result; } public void inorder(TreeNode root, List result){ if(root == null){ return; } inorder(root.left, result); result.add(root.val); inorder(root.right,result); }}-
题解2（迭代法）：
/** * Definition for a binary tree node. * 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; * } * } */class Solution { public List inorderTraversal(TreeNode root) { //记录结果 List result = new ArrayList(); //若传入root为空栈，则返回空 if(root == null){ return result; } //传入非空栈(至少有根结点) //当前指针 TreeNode cur = root; //辅助栈 Stack st = new Stack(); //辅助栈非空或者当前指针未指向树最底层 while(!st.isEmpty() || cur != null){ //如果指针未访问到最底层 if(cur != null){ //入栈当前指针元素，指针处理左分支 st.push(cur); cur = cur.left; }else{ //若访问到最底层，转而向右处理 cur = st.pop(); result.add(cur.val); cur = cur.right; } } return result; }}145、二叉树的后序遍历
- 刷题https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
-
题解1（递归法）：
/** * Definition for a binary tree node. * 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; * } * } */class Solution { public List postorderTraversal(TreeNode root) { List result = new ArrayList(); postorder(root, result); return result; } public void postorder(TreeNode root, List result){ if(root == null){ return; } postorder(root.left, result); postorder(root.right, result); result.add(root.val); }}-
题解2（迭代法）：
/** * Definition for a binary tree node. * 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; * } * } */class Solution { public List postorderTraversal(TreeNode root) { //后序遍历与前序相反即可 //中-左-右 -> 中-右-左 -> 左-右-中 //即:左右孩子入栈顺序翻转，最后把result翻转即可，其余与前序大致相同 List result = new ArrayList(); if(root == null){ return result; } Stack st = new Stack(); st.push(root); while(!st.isEmpty()){ TreeNode cur = st.pop(); result.add(cur.val); if(cur.left != null){ st.push(cur.left); } if(cur.right != null){ st.push(cur.right); } } Collections.reverse(result); return result; }}相关Java语法基础：
关于Java中Collection的用法及示例：
在Java中，Collection是一个接口，它代表一组对象，这些对象被称为元素。Collection接口提供了一系列操作元素的方法，包括添加、删除、查找和遍历等操作。
常见的Collection接口的实现类包括List、Set和Queue等，它们分别代表有序集合、无序集合和队列。
使用Collection接口的一般步骤如下：
-
创建Collection对象：使用实现了Collection接口的类来创建一个集合对象，例如ArrayList、HashSet等。
-
添加元素：使用add()方法向集合中添加元素。
-
删除元素：使用remove()方法从集合中删除元素。
-
查找元素：使用contains()方法或者其他查找方法来查找集合中是否包含某个元素。
-
遍历集合：使用迭代器（Iterator）或者增强for循环来遍历集合中的元素。
除了上述基本操作外，Collection接口还提供了其他一些常用的方法，例如size()方法用于获取集合中元素的个数，isEmpty()方法用于判断集合是否为空，clear()方法用于清空集合中的所有元素等。
当使用Java中的Collection时，通常需要先导入java.util包。接下来是一些常见的Collection接口的用法和示例：
1、List List是一个有序集合，允许重复元素。
import java.util.List;import java.util.ArrayList;List list = new ArrayList();list.add("Apple");list.add("Banana");list.add("Orange");System.out.println(list); // [Apple, Banana, Orange]list.remove("Banana");System.out.println(list); // [Apple, Orange]System.out.println(list.contains("Apple")); // truefor (String fruit : list) { System.out.println(fruit);}2、Set Set是一个不允许重复元素的无序集合。
import java.util.Set;import java.util.HashSet;Set set = new HashSet();set.add("Apple");set.add("Banana");set.add("Orange");System.out.println(set); // [Orange, Apple, Banana]set.remove("Banana");System.out.println(set); // [Orange, Apple]System.out.println(set.contains("Apple")); // truefor (String fruit : set) { System.out.println(fruit);}3、Map Map是一种键值对的集合。
import java.util.Map;import java.util.HashMap;Map map = new HashMap();map.put("Apple", 10);map.put("Banana", 20);map.put("Orange", 15);System.out.println(map); // {Orange=15, Apple=10, Banana=20}map.remove("Banana");System.out.println(map); // {Orange=15, Apple=10}System.out.println(map.containsKey("Apple")); // trueSystem.out.println(map.containsValue(15)); // truefor (Map.Entry entry : map.entrySet()) { System.out.println(entry.getKey() + " : " + entry.getValue());}在Java中，可以使用Collections类的reverse()方法来反转List中的元素顺序。以下是使用reverse()方法的示例：
import java.util.List;import java.util.ArrayList;import java.util.Collections;public class ReverseExample { public static void main(String[] args) { List list = new ArrayList(); list.add("Apple"); list.add("Banana"); list.add("Orange"); System.out.println("Original List: " + list); // [Apple, Banana, Orange] Collections.reverse(list); System.out.println("Reversed List: " + list); // [Orange, Banana, Apple] }}在这个示例中，我们首先创建了一个ArrayList，并向其中添加了一些元素。然后我们使用Collections.reverse()方法来反转列表中元素的顺序。最后打印出反转后的列表，可以看到列表中的元素顺序已经被颠倒过来了。
需要注意的是，reverse()方法只适用于List接口的实现类，而不适用于Set或者Queue。如果想对其他类型的集合进行元素顺序的反转，需要先将其转换为List类型，然后再使用reverse()方法。
Stack定义及基础操作：
在Java中，Stack是一种后进先出（LIFO）的数据结构，它可以存储一组元素，并且只能在栈顶进行插入和删除操作。
Stack的基础操作包括：
- push(element)：将元素压入栈顶。
- pop()：从栈顶弹出一个元素并返回。
- peek()：返回栈顶元素但不移除。
- empty()：判断栈是否为空。
- search(element)：查找元素在栈中的位置。
以下是一个简单的示例代码：
import java.util.Stack;public class Main { public static void main(String[] args) { Stack stack = new Stack(); // 压入元素 stack.push(1); stack.push(2); stack.push(3); // 弹出元素 int element = stack.pop(); System.out.println("弹出的元素：" + element); // 获取栈顶元素 int topElement = stack.peek(); System.out.println("栈顶元素：" + topElement); // 判断栈是否为空 boolean isEmpty = stack.empty(); System.out.println("栈是否为空：" + isEmpty); // 查找元素位置 int position = stack.search(2); System.out.println("元素2在栈中的位置：" + position); }}ArrayList定义及基础操作：
在Java中，ArrayList是一种动态数组，它可以存储一组元素，并且可以动态调整大小。
ArrayList的基础操作包括：
- add(element)：向列表末尾添加元素。
- add(index, element)：在指定位置插入元素。
- get(index)：获取指定位置的元素。
- remove(index)：移除指定位置的元素。
- size()：返回列表的大小。
- isEmpty()：判断列表是否为空。
- contains(element)：判断列表是否包含指定元素。
- indexOf(element)：返回指定元素在列表中的位置。
以下是一个简单的示例代码：
import java.util.ArrayList;public class Main { public static void main(String[] args) { ArrayList list = new ArrayList(); // 向列表末尾添加元素 list.add("Apple"); list.add("Banana"); list.add("Orange"); // 在指定位置插入元素 list.add(1, "Grape"); // 获取指定位置的元素 String element = list.get(2); System.out.println("获取的元素：" + element); // 移除指定位置的元素 list.remove(0); // 返回列表的大小 int size = list.size(); System.out.println("列表的大小：" + size); // 判断列表是否为空 boolean isEmpty = list.isEmpty(); System.out.println("列表是否为空：" + isEmpty); // 判断列表是否包含指定元素 boolean contains = list.contains("Banana"); System.out.println("列表是否包含Banana：" + contains); // 返回指定元素在列表中的位置 int index = list.indexOf("Orange"); System.out.println("Orange在列表中的位置：" + index); }} -
-
-
-
