【LeetCode刷题记录】104. 二叉树的最大深度

104 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：
输入：root = [1,null,2]
输出：2

提示：
树中节点的数量在 $[0,10^4]$ 区间内。
$-100<=Node.val<=100$

思路

（1）深度优先遍历DFS：
按深度往下遍历，先遍历左子树计算其深度l，再遍历右子树计算其深度r，那么该二叉树的最大深度就是max(l,r)+1。左右子树的深度也是如此计算，故用递归计算左右子树的最大深度+1即可。
（2）广度优先遍历BFS：
即二叉树的层次遍历，因为计算层数就可知道深度。不同于普通的层次遍历每次只取一个队列中的一个节点，计算深度需要每次取当前队列中的所有节点进行遍历。用ans记录深度。

代码

法一：

//DFS
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

法二：

// BFS
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* now = q.front();
                q.pop();
                if (now->left) {
                    q.push(now->left);
                }
                if (now->right) {
                    q.push(now->right);
                }
            }
            ans++;
        }
        return ans;
    }
};