题. 二叉树的深度
输入一棵二叉树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
数据范围
树中节点数量 [0,500]。
样例
输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \
12 2
/ \
6 4
输出：3【题解】--- DFS、BFS
二叉树（Binary tree） 是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
__二叉树是n个有限元素的集合__，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
关于二叉树的性质：
- 性质1：二叉树的第i层上至多有2i-1（i≥1）个节点 。
- 性质2：深度为h的二叉树中至多含有2h-1个节点 。
- 性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1 。
- 性质4：具有n个节点的满二叉树深为log2n+1。
- 性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点 。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点 。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。
对于本题： 有两种方法。
方法1：利用dfs记录当前层，遇到叶子更新全局最大层数。
方法2：利用bfs 每次都把上一层弹出。
简易题，具体解法见代码。
C++代码实现：
class Solution {
public:
int ans=1;
int treeDepth(TreeNode* root) {
if(!root) return 0;
dfs(root,0);
return ans;
}
void dfs(TreeNode* r,int lev){
if(!r){
ans=max(lev,ans);
return;
}
dfs(r->left,lev+1);//写成lev++,需要恢复现场
dfs(r->right,lev+1);
}
};
// 方法二：
class Solution {
public:
int treeDepth(TreeNode* root){
if(!root) return 0;
queue<TreeNode*> q;
q.push(root);
int lev=0;
while(!q.empty()){
TreeNode* tail=q.back(),*head;//记录上一层的末尾
while(!q.empty()){
head=q.front();q.pop();
if(head->left) q.push(head->left);
if(head->right) q.push(head->right);
if(head==tail) break;//此时上一层都已经出队
}
lev++;
}
return lev;
}
};
