题目的主要信息：

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

方法一：递归（dfs）

具体做法：

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

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

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

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot == NULL) //空结点没有深度
            return 0;
        return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right)) + 1; //返回子树深度+1
    }
};

复杂度分析：

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

方法二：层次遍历（bfs）

具体做法：

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

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

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

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot == NULL) //空结点没有深度
            return 0;
        queue<TreeNode*> q; //队列维护层次后续结点
        q.push(pRoot); //根入队
        int res = 0; //记录深度
        while(!q.empty()){ //bfs
            int n = q.size(); //记录当前层有多少结点
            for(int i = 0; i < n; i++){ //遍历完这一层，再进入下一层
                TreeNode* node = q.front();
                q.pop();
                if(node->left) //添加下一层的左右结点
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            res++; //深度加1
        }
        return res;
    }
};

复杂度分析：

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