题目的主要信息：

• 输入一棵二叉树，求该树的深度
• 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度

方法一：递归（dfs）

具体做法：

对于一棵二叉树而言，其深度等于根结点这个1层+左子树和右子树深度的最大值，而每个子树我们都可以看成根节点，于是我们可以对这个问题划为子问题，利用递归来解决:

$roo{t}_{depth}=max(lef{t}_{depth},righ{t}_{depth})+1root\_\{depth\}\; =\; max(left\_\{depth\},\; right\_\{depth\})+1$

递归的终点就是遇到空结点的时候。而这样的递归其实也是深度优先遍历，每次先遍历到二叉树最深处，再往上相加。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) //空结点没有深度
            return 0;
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1; //返回子树深度+1
    }
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历二叉树每个结点
• 空间复杂度：$O(n)O(n)$，递归栈深度就是二叉树的高度，其中最坏情况是二叉树退化为链表，深度最大为$nn$

方法二：层次遍历（bfs）

具体做法：

我们还可以利用层次遍历，一般情况我们进行二叉树的层次遍历时会借助队列，我们会发现队列有这样一个性质：首先是根结点进入队列，队列长度为1，二叉树第一层也只有一个，当这个poll出去以后，后续加入进来的便是根结点的左右子结点，它有多少子结点，下一轮的队列就会长度就是多少，这个可以推广到后续每一层。

因此我们就可以每次统计当前的层的结点数即当前层的队列长度，然后将这些结点全部弹出队列，弹入的正是它们的子结点，这样一层一层地访问，我们就可以每过一层记录一次深度了。

注意看下图中，每次进入一个新层时，该层结点数就是队列中的元素个数：

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) //空结点没有深度
            return 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>(); //队列维护层次后续结点
        q.add(root); //根入队
        int res = 0; //记录深度
        while(!q.isEmpty()){ //bfs
            int n = q.size(); //记录当前层有多少结点
            for(int i = 0; i < n; i++){ //遍历完这一层，再进入下一层
                TreeNode node = q.poll();
                if(node.left != null) //添加下一层的左右结点
                    q.add(node.left);
                if(node.right != null)
                    q.add(node.right);
            }
            res++; //深度加1
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历二叉树每个结点
• 空间复杂度：$O(n)O(n)$，辅助队列的最大长度不会超过$nn$