输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
难度：易
计算二叉树深度的问题是基于二叉树的广度优先遍历，以下是递归和非递归 写法。
递归写法
public int TreeDepth(TreeNode root) {
if(root == null) return 0;// 递归出口
// 树的高度 = 左子树和右子树中高的那个 加1
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
非递归写法 计数器法
public int getDeep2(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 添加到队列中
int count = 1, depth = 0; // 初始化当层节点数，深度计数器
while (queue.size() != 0) {
TreeNode node = queue.poll();
count--;// 没读取一个节点，当前节点计数器-1
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
if (count == 0) {// 如果当前层读取完毕
depth++;// 深度+1
count = queue.size();// 重置计数器大小
}
}
return depth;
}
非递归写法 分层标志法
class Solution {
public int maxDepth(TreeNode root) {
// 广度遍历求深度
// 定义一个Queue，分层标志 null
// 或者设置分层标志
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
int deepth = 0;
queue.offer(root);
queue.offer(null);
while(queue.size() != 1){
TreeNode node = queue.poll();
if(node != null) {
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}else{
queue.offer(null);
deepth++;
}
}
return deepth+1;
}
}
