二叉树的四种遍历方法
二叉树主要有两种遍历方式（共四种遍历方法）：
- 深度优先遍历 DFS：先往深走，遇到叶子节点再往回走（利用栈先进后出的特性）
- 前序遍历（递归法 / 迭代法）
- 中序遍历（递归法 / 迭代法）
- 后序遍历（递归法 / 迭代法）
- 广度优先遍历 BFS：一层一层的去遍历（利用队列先进先出的特性）
- 层次遍历（迭代法）
事实上，这两种遍历是图论中最基本的两种遍历方式，后面在介绍图的时候 还会讲到
另外，这几种遍历方法的时间复杂度都是 O(N)，因为每个节点都被顺序遍历了一次嘛；而空间复杂度取决于树的高度，当树退化为单链表的时候，空间复杂度降到 O(LogN)，正常情况下，空间复杂度都是 O(LogN)
# 中序遍历
题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 递归
private List<Integer> res = new ArrayList<>();
// 递归
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
inorderTraversal(root.left);
res.add(root.val);
inorderTraversal(root.right);
return res;
}
# 迭代
二叉树的遍历总是从根节点开始的，对于中序遍历来说，当第 1 次到达根节点时，并不是马上遍历根节点，而是顺着指向左子节点的指针向下直到叶节点，也就是找到第 1 个真正被遍历的节点。
为了在一个节点被遍历之后能够接着回去遍历它的父节点，可以在顺着指向左子节点的指针遍历二叉树时把遇到的每个节点都添加到一个栈中。
当一个节点被遍历了之后，就可以从栈中得到它的父节点
剑指 Offer 的写法，感觉挺好理解的
// 迭代
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 工作指针
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
// 顺着指向左子节点的指针向下直到叶节点，找到第 1 个真正被遍历的节点
while (cur != null) {
// 为了在一个节点被遍历之后能够接着回去遍历它的父节点，可以在顺着指向左子节点的指针遍历二叉树时把遇到的每个节点都添加到一个栈中
stack.push(cur);
cur = cur.left; // 1. 往左走
}
// 当到达最左子节点之后再从栈中依次取出节点进行遍历
cur = stack.pop();
res.add(cur.val); // 2. 读取当前节点
// 按照中序遍历的顺序，在读取一个节点之后再读取它的右子树
cur = cur.right; // 3. 往右走
}
return res;
}
# 前序遍历
题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
# 递归
private List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
res.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return res;
}
# 迭代
前序遍历的迭代代码和中序遍历的迭代代码也很类似。它们之间唯一的区别是在顺着指向左子节点的指针向下移动时，前序遍历将遍历遇到的每个节点并将它添加在栈中。这是由前序遍历的顺序决定的，前序遍历是先遍历根节点再遍历它的左子节点。二叉树前序遍历的迭代代码如下所示：
// 迭代
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 工作指针
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
res.add(cur.val); // 1. 读取当前节点
stack.push(cur);
cur = cur.left; // 2. 往左走
}
cur = stack.pop();
cur = cur.right; // 3. 往右走
}
return res;
}
# 后序遍历
题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 递归
private List<Integer> res = new ArrayList<>();
// 递归
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
res.add(root.val);
postorderTraversal(root.left);
postorderTraversal(root.right);
return res;
}
# 迭代
后序遍历和前两种遍历代码也很类似，如它们都需要用到一个栈，而且代码的基本结构很相像，都有两个 while 循环并且它们的条件都一样。需要留意遍历当前节点的时机。
前序遍历一边顺着指向左子节点的指针移动一边遍历当前的节点，而中序遍历和后序遍历则顺着指向左子节点的指针移动时只将节点放入栈中，并不遍历遇到的节点。只有当到达最左子节点之后再从栈中取出节点遍历。
后序遍历最复杂，还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为当前节点的右子节点来决定此时是否可以遍历当前的节点。
// 迭代
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 工作指针
TreeNode cur = root;
// 存储当前读取到的节点的前一个节点
TreeNode pre = null;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left; // 1.往左走
}
// 如果当前到达的节点 cur 有右子节点并且右子节点不是前一个遍历的节点，则表示它有右子树并且右子树还没有遍历过
// 按照后序遍历的顺序，应该先遍历它的右子树，因此把变量 cur 指向它的右子节点
cur = stack.peek();
if (cur.right != null && cur.right != pre) {
cur = cur.right; // 2. 往右走（然后又会进入下一个 while 循环然后走到最左边）
}
// 如果变量 cur 指向的节点没有右子树或它的右子树已经遍历过，则按照后序遍历的顺序此时可以读取这个节点，于是把它出栈并读取它
else {
stack.pop();
res.add(cur.val); // 3. 读取当前节点
// 在准备读取下一个节点之前，把 pre 指向当前读取的节点
pre = cur;
// 下一个读取的节点一定是 cur 的父节点，而父节点之前已经存放到栈中，所以将变量 cur 重置为 null 就行了
cur = null;
}
}
return res;
}
# 层次遍历
题目链接：
- 剑指 Offer 32 - I. 从上到下打印二叉树 (opens new window)
- 剑指 Offer 32 - II. 从上到下打印二叉树 II (opens new window)
- 102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
给你一个二叉树，请你返回其按 层序遍历 得到的节点值（即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
层次遍历用队列实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>(); // 存储遍历结果
Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列
if (root == null) {
return res;
}
queue.offer(root); // 根节点入队
while (!queue.isEmpty()) {
List<Integer> line = new ArrayList<>(); // 存储每层的节点
int sz = queue.size();
// 遍历当前层
for (int i = 0; i < sz; i ++) {
TreeNode cur = queue.poll();
line.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
// 将该层的遍历出来的所有节点加入结果集
res.add(line);
}
return res;
}
}
Tips，如果我们不需要这样一层一层清晰的结果，比如只需要返回
List<Integer>这种格式的话，其实 while 内部的 for 循环可以去掉，代码会看起来更简洁（当然不去也行~）：class Solution { public List<Integer> levelOrder(TreeNode root) { List<Integer> res = new ArrayList<>(); // 存储遍历结果 Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列 if (root == null) { return res; } queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { TreeNode cur = queue.poll(); res.add(cur.val); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } return res; } }
🎁 公众号
各位小伙伴大家好呀，叫我小牛肉就行，目前在读东南大学硕士，上方扫码关注公众号「飞天小牛肉」，与你分享我的成长历程与技术感悟~