题解 | #二叉树的最大深度#

题目的主要信息：

给定一棵二叉树的根节点，求这棵树的最大深度
深度是指树的根节点到任一叶子节点路径上节点的数量
最大深度是所有叶子节点的深度的最大值
叶子节点是指没有子节点的节点

方法一：递归

具体做法：

最大深度是所有叶子节点的深度的最大值，深度是指树的根节点到任一叶子节点路径上节点的数量，因此从根节点每次往下一层深度就会加1。因此二叉树的深度就等于根结点这个1层加上左子树和右子树深度的最大值，即 $root_{depth} = max(left_{depth}, right_{depth})+1$ 。而每个子树我们都可以看成一个根节点，继续用上述方法求的深度，于是我们可以对这个问题划为子问题，利用递归来解决：

终止条件： 当进入叶子节点后，再进入子节点，即为空，没有深度可言，返回0.
返回值： 每一级按照上述公式，返回两边子树深度的最大值加上本级的深度，即加1.
本级任务： 每一级的任务就是进入左右子树，求左右子树的深度。

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

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历整棵二叉树
空间复杂度： $O (n)$ ，最坏情况下，二叉树化为链表，递归栈深度最大为 $n$

方法二：层次遍历

具体做法：

既然是统计二叉树的最大深度，除了根据路径到达从根节点到达最远的叶子节点以外，我们还可以分层统计。对于一棵二叉树而言，必然是一层一层的，那一层就是一个深度，有的层可能会很多节点，有的层如根节点或者最远的叶子节点，只有一个节点，但是不管多少个节点，它们都是一层。因此我们可以使用层次遍历，二叉树的层次遍历就是从上到下按层遍历，每层从左到右，我们只要每层统计层数即是深度。

step 1：既然是层次遍历，我们遍历完一层要怎么进入下一层，可以用队列记录这一层中节点的子节点。队列类似栈，是一个先进先出的数据结构，可以理解为我们平时的食堂打饭的排队。因为每层都是按照从左到右开始访问的，那自然记录的子节点也是从左到右，那我们从队列出来的时候也是从左到右，完美契合。
step 2：在刚刚进入某一层的时候，队列中的元素个数就是当前层的节点数。比如第一层，根节点先入队，队列中只有一个节点，对应第一层只有一个节点，第一层访问结束后，它的子节点刚好都加入了队列，此时队列中的元素个数就是下一层的节点数。因此遍历的时候，每层开始统计该层个数，然后遍历相应节点数，精准进入下一层。
step 3：遍历完一层就可以节点深度就可以加1，

具体过程可以参考如下图示： alt

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) //空结点没有深度
            return 0;
        queue<TreeNode*> q; //队列维护层次后续结点
        q.push(root); //根入队
        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)$ ，其中 $n$ 为二叉树的节点数，遍历整棵二叉树
空间复杂度： $O (n)$ ，辅助队列的空间最坏为 $n$