算法

(DFS) $O(n)$

• 思路：这道题用DFS（深度优先搜索）来解答。我们知道，每个节点的深度与它左右子树的深度有关，且等于其左右子树最大深度值加上 1。

• 递归设计：

  1）. 递归条件: 对于当前节点root，我们求出左右子树的深度的最大值，再加1表示当前节点的深度，返回该数值，即为以root为根节点的树的最大深度。
  2）. 终止条件：当前节点为空时，认为树深为0。

C++ 代码

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return max(leftDepth, rightDepth) + 1;
    }
};

Java 代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }
}