二叉树通常是用来在内存中存储大量数据的，而数据存储的目的自然是为了后面的查询。对于普通二叉树来说，查询其实就是逐个遍历二叉树中元素的过程，这也就是二叉树的遍历。
理解二叉树的结构对理解如何遍历二叉树有非常好的帮助，下面我们先看一下二叉树长什么样。如图1所示，每个二叉树都有一个树根，而每个节点最多有两个子节点（可以有一个或者没有）。如果某个节点没有子节点，那么这个节点称为叶子节点。
image
二叉树最大的特点是每个节点的子节点及其下的内容又是一个二叉树。如图1所示，根节点1的左右子节点其实又分别是两个二叉树。正是二叉树的这个特点，因此二叉树特别适合通过函数递归调用的方式实现遍历。
二叉树的遍历
根据对二叉树中节点访问顺序的不同，可以将二叉树的遍历分为前序遍历、中序遍历、后序遍历和层序遍历。遍历的顺序是以当前节点为参考的，前序遍历就是先遍历当前节点，然后遍历左右子节点。中序遍历是先遍历左子节点，然后遍历当前节点，再然后遍历右子节点（当然左右子节点的遍历可以反过来）。后序遍历则是先遍历左右子节点，然后遍历当前节点。
图2 二叉树的遍历
以中序遍历为例，下面是C语言的实现代码。
图3 中序遍历实现
关于二叉树遍历比较简单，这些内容都是之前学过的，因此本文就不再赘述了。下面我们重点介绍在基础遍历算法上延伸的相关面试题。
遍历相关面试题精解
1. 计算二叉树的左叶子之和
计算给定二叉树的所有左叶子之和。这里认清目标对象，有两点需要注意：一点是目标对象是叶子节点，另外一点是左叶子节点。分析之后，我们知道本题其实是对二叉树进行遍历，并找到所有左叶子，并将左叶子的值进行累加。假设我们给出的题目函数原型如下所示，输入是一个二叉树，输出是一个整数。
为了便于理解，我们举例说明一下。如图3所示的二叉树，在这个二叉树中，有两个左叶子，分别是 9 和 13，所以返回 22。
图4 二叉树实例
二叉树并非都是完美的，比如下面这个二叉树（图4）。某些节点的子节点可能并不存在，此时需要在代码逻辑中加以注意。
image
经过上述分析，我们给出下面代码实现。
图6 题目代码实现
本题并不复杂，是二叉树遍历中最简单的面试题了，其核心是要注意对返回条件的判断。上述算法实现中通过一个具有传址参数的辅助函数实现了累加和，其实也可以不用这个参数，大家可以考虑一下如何解决。
2. 二叉树的最大深度
给定一个二叉树，找出其最大深度。首先需要搞清楚最大深度的定义。所谓二叉树的最大深度，是根节点到最远叶子节点的最长路径上的节点数量。
我们将上例中的二叉树拿过来作为例子，如图6所示。可以看到该二叉树的最大深度是4，也就是10->8->11->9或者10->3->13->19。
图6 二叉树实例
那么具体应该怎么计算二叉树的最大深度呢？试想，如果我们以根节点为参考，不考虑左右子树长什么样。那么整棵树的最大深度就是左右子树的最大深度中的大者加上根节点。根据二叉树的性质，我们层层递推，一直可以到叶子节点。
图7 二叉树深度计算
这里的核心就是返回条件。对于叶子节点其深度就是1，可以直接返回。而非叶子节点其深度需要根据左右子树进行计算。比如下面一个子树，11为该子树的根节点，左子树为叶子节点，没有右子树。因此，我们可以根据前面的思路计算出该子树的最大深度为2。依次类推，可以从下往上计算出整颗树的最大深度。
图8 节点深度计算
根据上面的思路，我们可以很容易的写出代码，具体如下所示。
如果我们将题目调整一下，求二叉树的最小深度，这个怎么实现？大家思考一下如何解决。
其它二叉树遍历面试题
二叉树遍历相关的面试题很多，很难一篇文章介绍全。下面是在面试中常见的题目汇总，我们后续会一一详细介绍。
1. 二叉树的中序遍历
2. 相同的树
3.对称二叉树
4.二叉树的层序遍历
5. 二叉树锯齿层次遍历
6.二叉树最小深度
7.翻转二叉树
8.搜索二叉树转累加树
9.合并二叉树
10.从根到叶子的二叉树之和
11.单值二叉树
网友评论