剑指Offer_编程题——二叉树的深度
题目描述：
输入一颗二叉树，求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径，最长路径为树的深度。
具体要求：
时间限制： C/C++ 1秒，其他语言2秒
空间限制： C/C++32M，其他语言64M
具体实现
背景知识介绍在开始做本题之前我们先给大家介绍**二叉树树的遍历：**
先序遍历、
中序遍历、
后序遍历以及
层次遍历。二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。
1、前序遍历，先检查
根节点，然后递归遍历
左子树和
右子树2、中序遍历，先遍历
左子树，然后检查
根节点，最后遍历
右子树3、后序遍历，先递归遍历
左右子树，然后检查
根节点4、层次遍历，从
第一层开始，
一层一层往下遍历
我们以
10,5,19,4,8,13,24为例，用动画详细介绍这四种遍历：
案例
1、前序遍历 前序遍历
a：输出当前节点值10，然后输出左子树，最后输出右子树；
b、对于其左子树来说，同样以这样的顺序，则先输出5，然后输出左子树4，最后输出右子树8；
c、对于其右子树，同样以这样的顺序，则先输出19，然后输出左子树13，最后输出右子树24；
最终得到前序遍历输出为：
10,5,4,8,19,13,24。 2、中序遍历 中序遍历
a：先输出左子树，然后输出当前节点13，最后输出右子树；
b：对于其左子树来说，同样以这样的顺序，则先输出左子树16，然后输出节点值22，最后输出右子树28；
c：对于其右子树，同样以这样的顺序，则先,输出左子树29，然后输出节点值30，最后输出右子树43；
最终得到中序遍历输出为：
13 16 22 28 29 30 43。我们发现
二叉查找树的中序遍历输出就是排序后的结果。因此二叉查找树也叫二叉搜索树或者二叉排序树。
3、后序遍历 后序遍历
a：先输出左子树，然后输出右子树，最后输出节点值13
b：对于其左子树来说，同样以这样的顺序，则先输出左子树22，然后输出右子树16，最后输出节点值29；
c：对于其右子树，同样以这样的顺序，则先,输出左子树43，然后输出右子树30，最后输出节点值28
最终得到后序遍历输出为：
13 22 16 29 43 30 28。 5、层次遍历 a：遍历第一层，输出10
b：遍历第二层，输出5,19
c：遍历第三层，输出4,8,13,24
最终得到层次遍历输出为： 10，5,19,4,8,13,24 。
不过虽然看起来过程很简单，但是代码实现却不能像前面三种深度优先遍历方式那样 直接使用递归，它更好的方式是借助一个具有 先入先出特点的队列（队列可参考队列-C语言实现）。以三个节点为例，我们先将根节点入队，然后分别入队左右孩子节点，最后输出队列内容，那么它的顺序就是层次遍历的顺序了。
注意：由于中序遍历和后序遍历中的动图是.webp格式，知乎不支持该格式，因此重新找了相关的动图，不过不妨碍中序遍历和后序遍历的理解。如果想看配套的动图可以看这篇文章。
具体实现
本题主要是求二叉树的深度，其实首先要进行二叉树的遍历，本题可以通过先序遍历、层次遍历、还可以用作递归。具体实现如下：
1、首先我们进行层次遍历
import
代码效果图如图所示：
正如我们之前的文章中提到，如果在牛客网中我们以上代码可以直接编译通过，因为它给我们定义了节点TreeNode，但如果在本地编译器(IDEA)中，我们得自己定义该节点，具体实现如下：
public
2、接下来，我们用递归来解决该题，其实任意的二叉树均可以看作root----left----right。具体实现如下：
public
代码效果图如图所示：
找到左右子树最大深度+1即可，递归的终止条件是空节点的深度是0。其实与我们刚才的递归算法很类似，具体用python实现如下：
class
代码效果图如图所示：
用python实现TreeNode结构：
class
3、然后我们用先序遍历来解决该题。实际上线找右子树的最大高度，再找左子树的最大高度。当然我们也可以先左子树进栈，然后右子树进栈，也就是先找左子树的最大高度，再找右子树的最大高度。具体实现如下：
import
代码效果图如图所示：
最后一种就是暴力法，具体实现如下：
public
代码效果图如图所示：
总结
本道题主要考察二叉树的深度，本题直截了当，思路清晰。很显然考察的是二叉树的四种遍历以及递归在二叉树中的使用，我们之前的很多二叉树的题目中，均用到了递归，因此，本题给出了四种解法来解决此题，并且在解题之前用动画的形式详细的为大家介绍了二叉树的四种遍历方法。因此，我们在做题的时候，应该多次尝试各种方法，扩展自己的思维，写出优质的代码。总之，我们要继续加油，争取早日找到工作，Good Luck！！！
参考文献
[1]动画：二叉树遍历的多种姿势
[2]COSCHINA
[3]Chosen_Xxx