转自景禹

今天我们谈一谈二叉树的四种遍历方式，看完保准让你对二叉树的遍历一网打尽。

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

关于二叉树遍历的定义中有两个关键词：次序和访问。

二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。

树的结点之间不存在唯一的前驱和后继这样的关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。（这就像我们的人生路上一次次的抉择，考研还是工作！当然我们的选择不是像二叉树的选择，要么左，要么右，但我们既然选择了，一定要努力证明自己选择的正确性！）

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：前序遍历、中序遍历、后序遍历和层序遍历。下面分别看一下每一种遍历方式。

01.

前序遍历

单链表若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

我们可以简记为：中 → 左 → 右。我们先看一下动画演示，然后再来分析具体的实现方式：

多看几遍，我相信你对二叉树的先序遍历会有一定的概念，不急，等我们看完代码，我想你会完全理解的。

对于二叉树的先序遍历，我们一般可以采用两种方式：递归 和 迭代。

谈到递归实现，景禹推荐不熟悉的朋友看看《数据结构与算法之递归+分治》这篇文章，里面的解释较为详细，看下面的代码注意注释，标明了递归的三要素！！

代码语言：javascript代码运行次数：0运行复制class Solution {

ArrayList list = new ArrayList<>();

//第一要素：明确你这个函数想要干什么

//函数功能：进行先序遍历二叉树

public List preorderTraversal(TreeNode root) {

//第二要素：寻找递归结束条件

if(root == null)

return;

//第三要素：找出函数的等价关系式

list.add(root.val);//中

if(root.left != null)//左

preorderTraversal(root.left);

if(root.right != null)//右

preorderTraversal(root.right);

return list;

}

}递归的执行过程中产生的递归树画起来不方便，而且存在大量冗余，景禹就不给大家演示了，而且在面试的时候，建议在给面试官给出递归的解法之后，能够再使用迭代进行解答。

上面的视频是二叉树的前序遍历的动画演示，你可以结合动画来看下面的迭代实现，需要注意的是，迭代实现中我们是先将根结点的右子节点入栈，然后在将左子节点入栈，这是因为栈的后进先出特性才如此处理的：

代码语言：javascript代码运行次数：0运行复制class Solution {

public List preorderTraversal(TreeNode root) {

LinkedList stack = new LinkedList<>();

LinkedList res = new LinkedList<>();

if (root == null) {

return res;

}

stack.add(root);

while (!stack.isEmpty()) {

TreeNode node = stack.pollLast();

res.add(node.val);

if (node.right != null) {

stack.add(node.right);

}

if (node.left != null) {

stack.add(node.left);

}

}

return res;

}

}02.

中序遍历

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），先中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

我们可以简记为：左 → 中 → 右。我们同样先看一下动画演示，然后再来分析具体的实现方式（由于微信公众号后台对gif图片大小有限制，如果觉着下面的gif动画不够清晰，可以视频号 景禹 中观看）：

对于中序遍历，景禹专门还制作下图：

图中左侧表示将树不断地划分，直到包含一个顶点；右侧就是你对一棵树进行拆分后得到一颗一颗的子树，然后将这一颗一颗的子树按照如下的GIF动画进行合并，就得到了我们的中序遍历结果，对于前序遍历和后序遍历也是一样的道理！

同样，我们采用递归和迭代两种方式进行实现，其中递归只需要将前序遍历中res.add(root.val)移动到两个if语句中间即可。

代码语言：javascript代码运行次数：0运行复制class Solution {

ArrayList list = new ArrayList<>();

public List inorderTraversal(TreeNode root) {

if(root == null)

return list;

if(root.left != null) //左

inorderTraversal(root.left);

list.add(root.val); //中

if(root.right != null) //右

inorderTraversal(root.right);

return list;

}

}是不是觉着递归炒鸡简单呢？确实简单，不需要我们思考具体的执行过程，不过我们是学东西，再看一下迭代的实现。

中序遍历：左 → 中 → 右 ，所以外层while循环的内部我们增加了一个while循环，用于遍历到curr结点的最左侧结点，也就是当curr为空时，栈顶的元素为其子树的根结点，弹出栈顶元素并赋值给curr，然后将curr的右子结点赋值给自身；然后执行外层while循环，直到栈为空且curr为空。

代码语言：javascript代码运行次数：0运行复制public class Solution {

public List inorderTraversal(TreeNode root) {

List res = new ArrayList<>();

Stack stack = new Stack<>();

TreeNode curr = root;

while (curr != null || !stack.isEmpty()) {

while (curr != null) {

stack.push(curr);

curr = curr.left;

}

curr = stack.pop();

res.add(curr.val);

curr = curr.right;

}

return res;

}

}03.

后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点

我们可以简记为：左 → 右 → 中。先来看一下遍历的动画演示有一个直观的感受：

接着我们一起来看一下后序遍历的三种实现方式：递归、迭代和取巧！

二叉树后序遍历的递归实现相当简单，只需要将前序遍历中res.add(root.val)移动到两个if语句之后即可。

代码语言：javascript代码运行次数：0运行复制class Solution {

ArrayList list = new ArrayList<>();

public List postorderTraversal(TreeNode root) {

if(root == null)

return list;

if(root.left != null)//左

postorderTraversal(root.left);

if(root.right != null)//右

postorderTraversal(root.right);

list.add(root.val);中

return list;

}

}我们着重分析一下后序遍历的迭代和取巧的实现方式，首先来看一下迭代的实现方式的动画演示（该视频包含迭代和取巧的两种方法的动画演示）：

对照着上面的动画来看代码就轻松很多了，代码整体与中序遍历很相似，但需要注意其中两个点。第一，stack.peek()只是取出栈顶元素，要和stack.pop()弹出栈顶元素区分开来；第二，变量last用于保存当前栈顶所弹出的元素，判断 curr.right == last 是为了避免重复访问同一个元素而陷入死循环当中。

代码语言：javascript代码运行次数：0运行复制class Solution {

public List postorderTraversal(TreeNode root) {

List res = new LinkedList<>();

Stack stack = new Stack<>();

TreeNode curr = root;

TreeNode last = null;

while (curr != null || !stack.isEmpty()) {

while (curr != null) {

stack.push(curr);

curr = curr.left;

}

curr = stack.peek();

if (curr.right == null || curr.right == last) {

res.add(curr.val);

stack.pop();

last = curr;

curr = null;

} else {

curr = curr.right;

}

}

return res;

}

}最后我们看一下二叉树后序遍历一种取巧的实现方式，我们已知后序遍历的节点访问顺序为：左 → 右 → 中；我们将这个次序颠倒过来：中 → 右 → 左；有没有想到前序遍历的节点访问顺序呢？猜你也想到了，中 → 左 → 右；因此，我们可以将前序遍历代码中的压栈顺序进行调整，并将结果逆序输出就可以啦！(取巧的方法的动画在上面的视频中）

紧接着看代码，你绝对会有种豁然开朗的感觉，注意要逆序输出，只需要每次在链表的头部插入元素即可，此外，由于栈本身的特性，对于 中 → 右 → 左 ，我们应该现将左子节点入栈，再将右子节点入栈。

代码语言：javascript代码运行次数：0运行复制class Solution {

public List postorderTraversal(TreeNode root) {

LinkedList stack = new LinkedList<>();

LinkedList res = new LinkedList<>();

if (root == null) {

return res;

}

stack.add(root);

while (!stack.isEmpty()) {

TreeNode node = stack.pollLast();

res.addFirst(node.val);//每次在链表的头部插入元素

if (node.left != null) { //注意与前序对比着看

stack.add(node.left);

}

if (node.right != null) {

stack.add(node.right);

}

}

return res;

}

}04.

层序遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

层序遍历是最简单的一种遍历方式，在考试和面试中很少涉及，但我们也不放过那5%的可能。万一遇到了呢？

由于每篇图文只能放三个视频，迫不得已我将后序遍历的两种方法的动画合并到了一个视频中，层序遍历就不给大家动画演示了，不过后续都是上传到景禹的视频号当中。

我们直接看一下代码，层序遍历中我们首先定义了一个保存遍历结果的数组res，然后定义了一个用于保存每一层结点的队列，队列满足先进先出的特性，我们在入队的时候一定是先左子节点，再右子节点（这样才符合从左到右的顺序对结点逐个访问），整个过程包裹在一个while循环之中，直到队列为空。

代码语言：javascript代码运行次数：0运行复制class Solution {

public List> levelOrder(TreeNode root) {

// 创建二维数组接收每层的结点

List> res = new ArrayList<>();

if (root == null) {

return res;

}

// 创建队列依次存放每层的结点

Queue q = new LinkedList<>();

q.add(root);

while (!q.isEmpty()) {

// 创建临时数组来存放每一层的结点

List tmp = new ArrayList<>();

int len = q.size();

for (int i = 0; i < len; i++) {

// 定义 node 接收出队结点，然后加入数组 tmp 中

TreeNode node = q.poll();

tmp.add(node.val);

// 如果有左孩子，先将左孩子入队

if (node.left != null) {

q.add(node.left);

} //如果有右孩子，再将右孩子入队

if (node.right != null) {

q.add(node.right);

}

}

// 将tmp，也就是当前一层的节点对应的数组放入二维数组res中

res.add(tmp);

}

return res;

}

}除了上面使用队列进行迭代的处理方法之外，我们依旧可以使用递归的方式进行解决，注意递归函数helper增加了一个记录当前处理节点的层数：

代码语言：javascript代码运行次数：0运行复制class Solution {

List> res = new ArrayList>();

public void helper(TreeNode node, int level) {

// 从当前的level层开始，创建一个当前层的数组并放入二维数组res中

if (res.size() == level)

res.add(new ArrayList());

// 将当前层的节点添加到对应的level数组中

res.get(level).add(node.val);

// 处理下一层的孩子结点

if (node.left != null)

helper(node.left, level + 1);

if (node.right != null)

helper(node.right, level + 1);

}

public List> levelOrder(TreeNode root) {

if (root == null) return res;

helper(root, 0);

return res;

}

}05.

总结

二叉树的遍历包含四中遍历方法：前序遍历（中 → 左 → 右）、中序遍历（左 → 中 → 右）、后序遍历（左 → 右 → 中）和层序遍历。对于每一种遍历方式都可以使用递归的方式进行实现，其中前中后序还可以借助栈进行迭代实现，而层序遍历可以借助队列进行迭代实现。