LeetCode | 104.二叉树的最大深度

这次来写一下 LeetCode 的第 104 题，二叉树的最大深度。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

这也是一道关于二叉树的题目，题目中要求我们计算二叉树的最大深度，也就是从根节点到最远的叶子节点的层数。比较容易想到的方法就是对二叉树进行一次层次遍历，然后记录层数，直到遍历完所有节点，这样也就得到二叉树的最大深度。该题和 102 题的层次遍历的算法是相同的，只要在遍历的时候做计数就可以了。

题目中给出的 C++ 定义如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        
    }
};

题目中给出了二叉树的定义，给出了需要实现的函数的定义，我们只要实现 maxDepth 即可。

题目分析

二叉树就是每个节点最多可以有两个孩子节点，这两个孩子节点分别称为当前节点的左子树和右子树。该题目是要求计算最大深度，而题目中则写着要得到从根节点到最远叶子节点路径上的节点数量。其实题目中的描述是对题目的一个解释。

从题目来看，比较容易想到的算法就是直接使用层次进行遍历，二叉树的 层次遍历 相比于 二叉树的前序遍历、中序遍历 和 后序遍历 要稍微复杂一下。二叉树的前序遍历、中序遍历 和 后序遍历 可以简单的使用 递归 进行遍历，而 二叉树的层次遍历 则需要借助 队列 这个数据结构来完成。也就是为了遍历一种数据结构而引入了另外一种数据结构。简单的介绍一下二叉树的 层次遍历 的算法。

先来准备一个二叉树，二叉树如下图：

上图就是题目中给出的一棵二叉树，由于这棵树的深度不深，直接就可以看出有 3 层。当树比较深的时候，我们也可以用眼看、用手数。但是，计算机就不能像人这样做了，计算机需要人来写程序才能实现，需要通过一定的算法来进行计算了。我来画图演示一下对 二叉树 进行 层次遍历 的方法。

首先，需要准备一个可以充当队列的数据结构，这点很多语言都有相应的集合可以直接使用。然后从根节点开始入队，来看图。

根节点入队以后，就可以开始找根节点的 左孩子 和 右孩子 了，然后让它的 左孩子 和 右孩子 入队，并且让根节点出队，如下图。

在图中，红色表示已经 出队 的状态，绿色表示 入队 的状态。那么当前，根节点 的 左孩子 和 右孩子 入队，而 根节点 已经出队。这里为了可以直观的进行演示，队列中保存着节点的值，而实际队列中应该保存的是节点的地址，这点一定要注意。

那么，下一步，就需要让 队列 中的 节点9 和 节点20 的 左孩子 和 右孩子 也 入队。当然，节点9 是没有 左孩子 和 右孩子 的，那么将被忽略，直接让 节点20 的 左孩子 和 右孩子 入队。最后 节点9 和 节点20 需要 出队，如下图。

此时，节点20 的 左孩子 和 右孩子 都 入队 了。而 节点9 和 节点20 也 出队 了。此时就要将 节点15 和 节点7 的 左孩子 和 右孩子 进行 入队 了。但是，这两个节点都没有 左孩子 和 右孩子，因此也就没什么可入队的了，但是 节点15 和 节点7 仍然要 出队。

当 节点15 和 节点7 出队后，队列 变空了，整个 二叉树 的 层次遍历 就结束了。

上面的过程分析了 二叉树 的 层次遍历 的过程，那么 二叉树 的 深度 我们还是没有得到。其实，也已经得到了，只要我们在层次遍历的过程中，每遍历一层的时候进行一次计数就可以了。

代码实现

来具体看一下代码的实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        // 队列保存树的根节点
        queue<TreeNode*> que;
        que.push(root);

        int level = 0;
        // 遍历队列
        while (!que.empty()) {
            queue<TreeNode*> tmp;
            // 遍历每一层的节点
            while (!que.empty()) {
                TreeNode *p = que.front();
                que.pop();
                // 让当前层的左右节点入临时队
                if (p->left) {
                    tmp.push(p->left);
                }
                if (p->right) {
                    tmp.push(p->right);
                }
            }
            // 临时队的节点进入遍历的节点入队
            while (!tmp.empty()) {
                que.push(tmp.front());
                tmp.pop();
            }

            // 记录层数
            level ++;
        }

        return level;
    }
};

提交结果

在写完 maxDepth 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。