Link to LeetCode Problem

S1: DFS

递归地分别计算出左子树和右子树的高度，取最大值加一，就是当前二叉树的最大深度。

假设我们已经计算出了左子树的最大深度是 1，右子树的最大深度是 2，那整棵二叉树的的最大深度就是左右子树最大深度的最大值加上根节点，也就是 3。

接下来我们只需要递归地去计算左右子树的高度：

1. base condition: 首先在递归中很重要的事情就是找到递归的出口，在这道题目中，明显能想到的出口是：
   1. 当遍历到叶子节点的时候：if not root.left and not root.right，这时候我们需要 return 1。
   2. 还有一种情况是，当前遍历的节点为 null，这时候我们只需要 return 0 就好了。
2. 如果当前节点有左子树，需要递归计算左子树的高度 leftHeight = maxDepth(root.left)。
3. 如果当前节点有右子树，需要递归计算右子树的高度 rightHeight = maxDepth(root.right)。
4. 取左右子树最大高度的最大值，加上当前节点返回 max(leftHeight, rightHeight) + 1 即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (!root) return 0;
    if (!root.left && !root.right) return 1;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

• Time: $O(N)$，N 是二叉树的节点总数。
• Space: $O(logN)$，递归栈的空间，最坏的情况是二叉树退化成了链表，那递归栈的深度就成了 $O(N)$。

S2: BFS

前置：

102. 二叉树的层序遍历

也可用 BFS 的方式来遍历二叉树，每遍历一层深度就加一，再用一个全局变量来追踪深度最大值即可。

伪代码

新建一个队列来存放遍历的节点 把 root 推入队列 初始化 height 为 0

重复以下步骤： 记录当前层级的节点数 nodeCount (即队列中的节点数)

if nodeCount === 0: return height // 二叉树遍历结束 height++

// 遍历当前层级的每个节点 while nodeCount > 0: 出列一个节点，将它的左右子节点入列 nodeCount-- // 当前层级遍历结束，此时队列中的是下一层的节点

Recursive:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int maxD = 0;
        depth(root, 0, maxD);
        return maxD;
    }
    void depth(TreeNode* root, int curD, int& maxD) {
        if (root == nullptr) {
            maxD = max(maxD, curD);
            return;
        }
        depth(root->left, curD + 1, maxD);
        depth(root->right, curD + 1, maxD);
    }
};