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

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

具体做法：

step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.
step 2：递归分别计算左子树与右子树的深度。
step 3：当前深度为两个子树深度较大值再加1。

图示：

alt

Java实现代码：

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

C++实现代码：

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

Python实现代码

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # 空节点没有深度
        if not root: 
            return 0
        # 返回子树深度+1
        return max([self.maxDepth(root.left), self.maxDepth(root.right)]) + 1

复杂度分析：

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

方法二：层次遍历（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

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