第20篇-树的基础知识-二叉树遍历的递归与迭代写法

概述

学完 DFS 和 BFS 之后，我们进入第三阶段：树结构与经典策略。
树是一种非常重要的数据结构。
它不像数组、链表那样是简单的线性结构，而是一种天然的层级结构。

很多现实问题都可以抽象成树：

• 文件目录
• 公司组织架构
• 网页 DOM 结构
• 表达式语法树
• 搜索决策树

在算法题中，最常见的是二叉树。
二叉树题经常考察：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 最大深度
• 路径问题
• 二叉搜索树

这些题看起来很多，但基础都离不开一个核心能力：

遍历一棵树

这篇文章会从树的基本概念讲起，重点掌握二叉树的递归和迭代遍历写法。

学完这篇，你应该能看懂二叉树结构，并能独立写出前序、中序、后序和层序遍历。

核心概念：树到底是什么

树是一种由节点和边组成的数据结构。

一棵树通常长这样：

1 / \ 2 3 / \ 4 5

其中：

• 1是根节点
• 2和3是1的子节点
• 1是2和3的父节点
• 4和5是叶子节点
• 从1到4的路径是1 -> 2 -> 4

树有一个非常重要的特点：

除了根节点，每个节点都有且只有一个父节点

常见术语

什么是二叉树

二叉树是最常见的一类树。

它的定义是：

每个节点最多有两个子节点

这两个子节点通常叫：

• 左子节点
• 右子节点

Java 中常见的二叉树节点定义如下：

publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}

二叉树的每个节点最多有左右两个孩子，很多题都可以转化为“当前节点、左子树、右子树”之间的关系。

递归思维：为什么树天然适合递归

树结构天然适合递归。

因为一棵二叉树可以拆成：

根节点 + 左子树 + 右子树

而左子树和右子树本身又是二叉树。

这和递归思想完全一致：

大问题 = 当前节点要做的事 + 左子树问题 + 右子树问题

所以二叉树题常见递归模板是：

voiddfs(TreeNoderoot){if(root==null){return;}// 处理当前节点dfs(root.left);dfs(root.right);}

递归终止条件

树递归中最常见的终止条件是：

if(root==null){return;}

因为null表示空树。
当递归走到空节点时，就不需要继续往下走了。

二叉树题通常只需要想清楚当前节点怎么处理，剩下交给左右子树递归完成。

前序遍历：根、左、右

前序遍历的顺序是：

根节点 -> 左子树 -> 右子树

对于下面这棵树：

1 / \ 2 3 / \ 4 5

前序遍历结果是：

1, 2, 4, 5, 3

递归写法

importjava.util.ArrayList;importjava.util.List;classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();preorder(root,ans);returnans;}privatevoidpreorder(TreeNoderoot,List<Integer>ans){if(root==null){return;}ans.add(root.val);preorder(root.left,ans);preorder(root.right,ans);}}

执行过程

前序遍历先处理当前节点，再递归左子树，最后递归右子树。

访问 1 访问 2 访问 4 访问 5 访问 3

适用场景

前序遍历常用于：

• 复制一棵树
• 序列化二叉树
• 先处理父节点，再处理子节点的问题

前序遍历的特点是先访问根节点，再访问左右子树。

中序遍历：左、根、右

中序遍历的顺序是：

左子树 -> 根节点 -> 右子树

对于这棵树：

1 / \ 2 3 / \ 4 5

中序遍历结果是：

4, 2, 5, 1, 3

递归写法

importjava.util.ArrayList;importjava.util.List;classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();inorder(root,ans);returnans;}privatevoidinorder(TreeNoderoot,List<Integer>ans){if(root==null){return;}inorder(root.left,ans);ans.add(root.val);inorder(root.right,ans);}}

中序遍历和二叉搜索树

中序遍历在二叉搜索树中非常重要。

二叉搜索树的性质是：

左子树所有节点值 < 根节点值 < 右子树所有节点值

因此，对二叉搜索树进行中序遍历，会得到一个升序序列。

例如：

4 / \ 2 6 / \ / \ 1 3 5 7

中序遍历结果是：

1, 2, 3, 4, 5, 6, 7

中序遍历在普通二叉树中是一种遍历顺序，在二叉搜索树中常用来得到有序结果。

后序遍历：左、右、根

后序遍历的顺序是：

左子树 -> 右子树 -> 根节点

对于这棵树：

1 / \ 2 3 / \ 4 5

后序遍历结果是：

4, 5, 2, 3, 1

递归写法

importjava.util.ArrayList;importjava.util.List;classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();postorder(root,ans);returnans;}privatevoidpostorder(TreeNoderoot,List<Integer>ans){if(root==null){return;}postorder(root.left,ans);postorder(root.right,ans);ans.add(root.val);}}

适用场景

后序遍历常用于：

• 删除一棵树
• 计算子树信息
• 求二叉树最大深度
• 判断平衡二叉树
• 路径和、树形 DP

因为后序遍历是先处理左右子树，再处理当前节点。
所以当当前节点的答案依赖子树结果时，后序遍历非常合适。

后序遍历适合先拿到左右子树结果，再汇总当前节点答案的问题。

三种深度优先遍历对比

前序、中序、后序都属于 DFS。

它们的区别只在于：

根节点在什么时候被访问

可以记成：

前中后，说的是根节点的位置

前序遍历的迭代写法

递归遍历本质上使用的是系统调用栈。
我们也可以自己用栈来模拟递归。

前序遍历顺序是：

根 -> 左 -> 右

由于栈是后进先出，所以入栈时要先放右节点，再放左节点。

Java 代码实现

importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();if(root==null){returnans;}Stack<TreeNode>stack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();ans.add(node.val);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}returnans;}}

为什么先压右节点

栈的特点是后进先出。

如果希望左节点先被访问，就要让左节点后入栈。

所以顺序是：

先压右节点，再压左节点

这样弹出时就是：

左节点先出，右节点后出

中序遍历的迭代写法

中序遍历的顺序是：

左 -> 根 -> 右

迭代写法需要不断把左链压入栈中。

Java 代码实现

importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();Stack<TreeNode>stack=newStack<>();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.pop();ans.add(cur.val);cur=cur.right;}returnans;}}

代码怎么理解

中序遍历要先访问最左边的节点。
所以代码先一路向左：

while(cur!=null){stack.push(cur);cur=cur.left;}

当左边走不动了，再弹出栈顶节点访问。
访问完当前节点后，再转向右子树：

cur=cur.right;

中序迭代的核心是先把左链全部压栈，再依次弹出并转向右子树。

后序遍历的迭代写法

后序遍历顺序是：

左 -> 右 -> 根

它的迭代写法比前序和中序稍微复杂。
一种比较容易理解的方法是：

先得到 根 -> 右 -> 左 再反转成 左 -> 右 -> 根

Java 代码实现

importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;importjava.util.Stack;classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();if(root==null){returnans;}Stack<TreeNode>stack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();ans.add(node.val);if(node.left!=null){stack.push(node.left);}if(node.right!=null){stack.push(node.right);}}Collections.reverse(ans);returnans;}}

为什么这样能得到后序

上面的遍历过程访问顺序是：

根 -> 右 -> 左

把它反转后，就得到：

左 -> 右 -> 根

也就是后序遍历。

这种写法不是最节省操作的写法，但非常适合初学者理解。

层序遍历：一层一层访问节点

前序、中序、后序都是 DFS。
层序遍历则是 BFS。

层序遍历的顺序是：

从上到下，从左到右，一层一层访问节点

对于这棵树：

1 / \ 2 3 / \ 4 5

层序遍历结果是：

[ [1], [2, 3], [4, 5] ]

Java 代码实现

importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Queue;classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>ans=newArrayList<>();if(root==null){returnans;}Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}ans.add(level);}returnans;}}

为什么要记录size

size表示当前层有多少个节点。

每次只处理当前层的size个节点，就可以把每一层单独放进一个列表。

这和上一篇 BFS 中的按层统计是一模一样的思想。

层序遍历就是二叉树上的 BFS，队列用于保证节点按层访问。

复杂度分析：树遍历的成本

无论是前序、中序、后序，还是层序遍历，都会访问每个节点一次。

所以时间复杂度都是：

O(n)

其中n是树中节点数量。

空间复杂度要分情况：

• 递归 DFS：最坏O(n)，平衡树约O(log n)
• 迭代 DFS：栈空间最坏O(n)
• BFS 层序遍历：队列空间最坏O(n)

如果不计算返回答案数组，只计算额外辅助结构，上面的结论成立。

常见坑点：二叉树遍历最容易错在哪里

1. 忘记处理空树

空树输入非常常见。

递归写法中要有：

if(root==null){return;}

如果是返回列表的函数，也要能返回空列表。

2. 混淆前序、中序、后序

记住一句话：

前中后说的是根节点的位置

• 前序：根在前
• 中序：根在中间
• 后序：根在后

3. 迭代前序入栈顺序写反

前序遍历要求：

根 -> 左 -> 右

由于栈后进先出，所以应该：

先压右，再压左

4. 中序迭代忘记一路向左

中序迭代的关键是：

while(cur!=null){stack.push(cur);cur=cur.left;}

如果没有这个过程，就无法保证先访问左子树。

5. 层序遍历没有按层处理

如果题目要求返回每一层一个列表，就必须记录当前层节点数量：

intsize=queue.size();

否则所有节点会混在一个列表里。

模板总结：二叉树遍历常用写法

前序递归模板

voidpreorder(TreeNoderoot){if(root==null){return;}visit(root);preorder(root.left);preorder(root.right);}

中序递归模板

voidinorder(TreeNoderoot){if(root==null){return;}inorder(root.left);visit(root);inorder(root.right);}

后序递归模板

voidpostorder(TreeNoderoot){if(root==null){return;}postorder(root.left);postorder(root.right);visit(root);}

层序遍历模板

Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){TreeNodenode=queue.poll();if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}}

总结

二叉树是算法题中非常高频的数据结构。
它的很多题目都建立在遍历基础上。

你可以重点记住下面几句话：

• 二叉树每个节点最多有两个孩子
• 树天然适合递归，因为子树本身也是树
• 前序、中序、后序都属于 DFS
• 前中后说的是根节点的位置
• 前序是根、左、右
• 中序是左、根、右
• 后序是左、右、根
• 层序遍历是 BFS，需要用队列
• 递归写法更简洁，迭代写法本质是用栈模拟递归
• 中序遍历在二叉搜索树中会得到有序序列

掌握遍历之后，后面的最大深度、路径和、二叉搜索树等题目都会更容易理解。