文章目录
- 1 什么是二叉树
- 2 二叉树的存储
- 2.1 使用树节点类TreeNode存储（代码）
- 2.2 使用数组存储
- 3 二叉树的遍历
- 3.1 广度优先遍历
- 3.2 深度优先遍历
- 3.2.1 深度优先——前序遍历
- 3.2.2 深度优先——中序遍历
- 3.2.3 深度优先——后序遍历
- 3.3 代码实现
- 3.3.1 递归实现——深度优先遍历
- 3.3.2 非递归实现——深度优先遍历
- 3.3.2.1 前序遍历
- 3.3.2.2 中序遍历
- 3.3.2.3 后序遍历
- 3.3.2.4 非递归实现深度优先——统一写法★★★
- 力扣题144 二叉树的前序遍历
- 力扣题94 二叉树的中序遍历
- 力扣题145. 二叉树的后序遍历
🙊前言：本文章为瑞_系列专栏之《数据结构与算法》的二叉树篇。由于博主是从B站黑马程序员的《数据结构与算法》学习到的相关知识，所以本系列专栏主要针对该课程进行笔记总结和拓展，文中的部分原理及图解也是来源于黑马提供的资料。本文仅供大家交流、学习及研究使用，禁止用于商业用途，违者必究！
1 什么是二叉树
二叉树是一种树状结构：每个节点最多有两个孩子，左孩子和右孩子。
重要的二叉树结构：
- 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右。
- 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1 。
2 二叉树的存储
二叉树的存储方式一般分为：使用树节点类TreeNode存储、使用数组存储。
2.1 使用树节点类TreeNode存储（代码）
定义树节点与左、右孩子引用（TreeNode），参考代码如下：
public class TreeNode {
/**
* 节点值
*/
public int val;
/**
* 左孩子
*/
public TreeNode left;
/**
* 右孩子
*/
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(TreeNode left, int val, TreeNode right) {
this.left = left;
this.val = val;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(this.val);
}
}
2.2 使用数组存储
类似于使用数组实现堆，数组索引为 0 处即是根节点，索引为 1 处即是根节点的左孩子，索引为 2 处即是根节点的右孩子，没有元素则使用null表示。
若以 0 作为树的根，索引可以通过如下方式计算：
- 父 = floor((子 - 1) / 2)
- 左孩子 = 父 * 2 + 1
- 右孩子 = 父 * 2 + 2
瑞：实际过程中按照业务需求自己选定，两种存储的表示方式都可行，没有对错，只有适合和更适合
3 二叉树的遍历
遍历主要分为以下两种：
- 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历
- 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）
- pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
- in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
- post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点
3.1 广度优先遍历
广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历，即“Z”字型遍历，如下图：
用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树，如下表所示：
| 本轮开始时队列 | 本轮访问节点 |
|---|---|
| [1] | 1 |
| [2, 3] | 2 |
| [3, 4] | 3 |
| [4, 5, 6] | 4 |
| [5, 6] | 5 |
| [6, 7, 8] | 6 |
| [7, 8] | 7 |
| [8] | 8 |
| [] |
如上表所示，步骤为：
- 初始化，将根节点加入队列
- 循环处理队列中每个节点，直至队列为空
- 每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列
对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序
3.2 深度优先遍历
深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）
- pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
- in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
- post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点
3.2.1 深度优先——前序遍历
前序遍历规则：
- 先访问该节点
- 然后是左子树
- 最后是右子树
按照前序遍历规则，执行顺序为：先访问根节点1（打印1），然后访问根节点1的左子树2（打印2），然后访问2的左子树4（打印4），由于4左右子树为null，所以4访问结束。退回到2，2的左子树已经遍历完了，右子树为null，即2遍历结束。退回到1，1的左子树已经遍历结束，开始遍历1的右子树3（打印3），访问3的左子树5（打印5），5的左右子树为null，退回到3，访问3的右子树6（打印6），前序遍历结束。
前序遍历的结果为：1,2,4,3,5,6
瑞：根左右
3.2.2 深度优先——中序遍历
中序遍历规则：
- 先访问左子树
- 然后是该节点
- 最后是右子树
按照中序遍历规则，左子树没遍历完之前是不能打印该节点的值，所以执行顺序为：先访问根节点1（不打印），然后访问根节点1的左子树2（不打印），然后访问2的左子树4（不打印），由于4左子树为null，所以此时打印4（打印4），4的右子树为null，4遍历结束。退回到2，2的左子树已经遍历完了，所以此时打印2（打印2），2的右子树为null，即2遍历结束。退回到1，1的左子树已经遍历结束，此时打印1（打印1），开始遍历1的右子树3（不打印），访问3的左子树5（不打印），5的左子树为null，所以此时打印5（打印5），5的右子树为null，5遍历结束。退回到3，3的左子树已经遍历完了，所以此时打印3（打印3），开始访问3的右子树6（不打印），6的左子树为null，所以此时打印6（打印6），6的右子树为null，中序遍历结束。
中序遍历的结果为：4,2,1,5,3,6
瑞：左根右
3.2.3 深度优先——后序遍历
后序遍历规则：
- 先访问左子树
- 然后是右子树
- 最后是该节点
按照后序遍历规则，左右子树没遍历完之前是不能打印该节点的值，所以执行顺序为：先访问根节点1（不打印），然后访问根节点1的左子树2（不打印），然后访问2的左子树4（不打印），由于4左子树为null、右子树为null，所以此时打印4（打印4），4遍历结束。退回到2，2的左子树已经遍历完了，2的右子树为null，所以此时打印2（打印2），即2遍历结束。退回到1，1的左子树已经遍历结束，开始遍历1的右子树3（不打印），开始遍历1的右子树3（不打印），访问3的左子树5（不打印），5的左子树为null、5的右子树为null，所以此时打印5（打印5），5遍历结束。退回到3，3的左子树已经遍历完了，开始访问3的右子树6（不打印），6的左子树为null、6的右子树为null，所以此时打印6（打印6），6遍历结束。退回到3，3的左右子树遍历结束，所以此时打印3（打印3），退回到1，1的左右子树遍历结束，所以此时打印1（打印1） ，后序遍历结束。
后序遍历的结果为：4,2,5,6,3,1
瑞：左右根
瑞：不用特别死记硬背，因为左子树的遍历一定在右子树之前，所以前中后指的就是打印左右节点前该节点的打印顺序。比如前序遍历就是在左右子树遍历前（根左右），中序遍历就是左子树打印完之后打印该节点再打印右子树（左根右），后续遍历就是左右子树打印完再打印该节点（左右根），就是根的位置在左右子树的位置就是前中后序的区别
3.3 代码实现
以下实现均需要使用TreeNode类，在文章 2.1 使用树节点类TreeNode存储（代码）
构建本例中的树型结构的代码如下：
/*
1
/ \
2 3
/ / \
4 5 6
*/
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
3.3.1 递归实现——深度优先遍历
使用递归实现比较简单，代码如下：
public class TreeTraversal {
public static void main(String[] args) {
/*
1
/ \
2 3
/ / \
4 5 6
*/
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
System.out.print("前序遍历：\t");
preOrder(root);
System.out.println();
System.out.print("中序遍历：\t");
inOrder(root);
System.out.println();
System.out.print("后序遍历：\t");
postOrder(root);
System.out.println();
}
/**
* 前序遍历
*
* @param node 节点
*/
static void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + "\t"); // 值
preOrder(node.left); // 左
preOrder(node.right); // 右
}
/**
* 中序遍历
*
* @param node 节点
*/
static void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left); // 左
System.out.print(node.val + "\t"); // 值
inOrder(node.right); // 右
}
/**
* 后序遍历
*
* @param node 节点
*/
static void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left); // 左
postOrder(node.right); // 右
System.out.print(node.val + "\t"); // 值
}
}
以上代码运行结果：
前序遍历： 1 2 4 3 5 6
中序遍历： 4 2 1 5 3 6
后序遍历： 4 2 5 6 3 1
复杂度分析
- 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。
3.3.2 非递归实现——深度优先遍历
由于树型结构中没有保存父节点元素，所以需要使用栈（后进先出特性）来存储来回的路，本质上是在模拟递归，因为在递归的过程中使用了系统栈。可以使用自定义实现的栈类或者使用JDK1.8中自带的LinkedList<E>类，该类实现了Deque接口，即含有栈的相关方法。注意不建议使用Stack类，官方建议使用Deque接口及其实现类来实现的栈功能，具体原因本文不进行阐述。
3.3.2.1 前序遍历
LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
System.out.println(curr);
curr = curr.left;
} else {
TreeNode pop = stack.pop();
curr = pop.right;
}
}
3.3.2.2 中序遍历
LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode pop = stack.pop();
System.out.println(pop);
curr = pop.right;
}
}
3.3.2.3 后序遍历
LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
TreeNode pop = null;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
System.out.println(pop);
} else {
curr = peek.right;
}
}
}
对于后序遍历，向回走时，需要处理完右子树才能 pop 出栈。如何知道右子树处理完成呢？
- 如果栈顶元素的 right == null 表示没啥可处理的，可以出栈
- 如果栈顶元素的 right ≠null，
- 那么使用 lastPop 记录最近出栈的节点，即表示从这个节点向回走
- 如果栈顶元素的 right == lastPop 此时应当出栈
对于前、中两种遍历，实际以上代码从右子树向回走时，并未走完全程（stack 提前出栈了）后序遍历以上代码是走完全程了
3.3.2.4 非递归实现深度优先——统一写法★★★
下面是一种统一的写法，依据后序遍历修改，可根据前中后需求自定义修改
import java.util.LinkedList;
/**
* 非递归实现 深度优先遍历 三种遍历通用写法
*
* @author LiaoYuXing-Ray
* @version 1.0
* @createDate 2024/1/22 15:09
**/
public class RayTest {
public static void preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>(); // 栈
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
colorPrintln("前: " + curr.val, 31);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印
if (peek.right == null) {
colorPrintln("中: " + peek.val, 35);
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树处理完成, 对中序来说, 无需打印
else if (peek.right == pop) {
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树待处理, 对中序来说, 要在右子树处理之前打印
else {
colorPrintln("中: " + peek.val, 35);
curr = peek.right;
}
}
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
preorderTraversal(root);
}
/*
31 红
32 黄
33 橙
34 蓝
35 紫
36 绿
*/
public static void colorPrintln(String origin, int color) {
System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)
力扣题144 二叉树的前序遍历
Leetcode144. 二叉树的前序遍历
/**
* 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<Integer> preorderTraversal(TreeNode root) {
/*
* 栈
*/
LinkedList<TreeNode> stack = new LinkedList<>();
/*
* 代表当前节点
*/
TreeNode current = root;
/*
* 最近一次弹栈的元素
*/
TreeNode pop = null;
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty() || current != null) {
if (current != null) {
stack.push(current);
// 待处理左子树
result.add(current.val);
current = current.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
// 获取最近一次弹栈的元素
pop = stack.pop();
}
// 右子树处理完成
else if (peek.right == pop) {
// 获取最近一次弹栈的元素
pop = stack.pop();
}
// 待处理右子树
else {
current = peek.right;
}
}
}
return result;
}
}
力扣题94 二叉树的中序遍历
Leetcode94. 二叉树的中序遍历
/**
* 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<Integer> inorderTraversal(TreeNode root) {
/*
* 栈
*/
LinkedList<TreeNode> stack = new LinkedList<>();
/*
* 代表当前节点
*/
TreeNode current = root;
/*
* 最近一次弹栈的元素
*/
TreeNode pop = null;
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty() || current != null) {
if (current != null) {
stack.push(current);
// 待处理左子树
current = current.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
result.add(peek.val);
// 获取最近一次弹栈的元素
pop = stack.pop();
}
// 右子树处理完成
else if (peek.right == pop) {
// 获取最近一次弹栈的元素
pop = stack.pop();
}
// 待处理右子树
else {
result.add(peek.val);
current = peek.right;
}
}
}
return result;
}
}
力扣题145. 二叉树的后序遍历
Leetcode145. 二叉树的后序遍历
/**
* 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<Integer> postorderTraversal(TreeNode root) {
/*
* 栈
*/
LinkedList<TreeNode> stack = new LinkedList<>();
/*
* 代表当前节点
*/
TreeNode current = root;
/*
* 最近一次弹栈的元素
*/
TreeNode pop = null;
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty() || current != null) {
if (current != null) {
stack.push(current);
// 待处理左子树
current = current.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
// 获取最近一次弹栈的元素
pop = stack.pop();
result.add(pop.val);
}
// 右子树处理完成
else if (peek.right == pop) {
// 获取最近一次弹栈的元素
pop = stack.pop();
result.add(pop.val);
}
// 待处理右子树
else {
current = peek.right;
}
}
}
return result;
}
}
如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~
