LeetCode | 107.二叉树的层次遍历2

码农UP2U

发布于 2020-10-29 11:03:48

3280

发布于 2020-10-29 11:03:48

文章被收录于专栏：码农UP2U

这次来写一下 LeetCode 的第 107 题，二叉树的层次遍历2。

题目描述

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

这道题同样是二叉树的题目，也同样是二叉树的层次遍历的问题。但是最终的输出是一个二维数组，二维数组中每一维数组都保存着二叉树每层的节点值，而且是从树叶到树根的顺序的进行保存的。那么这道题目的重点除了是对二叉树进行层次遍历之外，还需要考虑对二叉树节点值的存储。

本次我使用 C++ 来完成这道题目，来看一下 LeetCode 给出的 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
    }
};

题目分析

关于二叉树的层次遍历，我在其他文章中已经写过了。二叉树的层次遍历需要借助队列来配合完成。初始化时，让二叉树的根节点入队，然后开始从队列中让队头的元素出队，并获得出队节点的左孩子和右孩子进行入队。按照这样的步骤来循环，直到队列为空，整个二叉树的层次遍历就完成了。

虽然其他文章介绍过二叉树的层次遍历，但是本次的二叉树遍历会把存储的方式进行介绍。

首先，准备一个二叉树，和一个队列，并初始化队列，也就是让根节点进入队列。

二叉树的根节点进入了队列中，然后开始循环。那么就开始让队头的节点3 出队，并找节点3 的左孩子和右孩子。找到的左孩子和右孩子就是节点9 和节点20，但是这两个孩子不能直接入队，如果直接入队，那么就会开始直接遍历二叉树的第二层节点了。在遍历第二层节点之前，我们需要让第一层的节点以一个一维数组的形式保存，并插入到要返回的二维数组当中。因此如下图。

当一维数组 [3] 进入要返回的二维数组后，临时队列的中的元素就要进入正式的队列当中了，如下图。

此时，队列中有节点9 和节点20，被标为红色的节点3 表示已经出队了。接着节点9 出队，节点9 没有左右孩子，那么让节点20 出队，让节点20 的左右孩子进入临时队列，让节点9 和节点20 以一位数组的形式插入到二维数组中，如下图。

从图中可以看出，[9, 20] 组成的数组在插入到二维数组的时候，是在二维数组的头部进行插入的。这样，在最后的输出时，就是从二叉树的叶子节点到二叉树的根进行输出了。

依次按照这样的方式进行循环，并保存每层的节点并插入到要返回的二维数组当中即可。

代码实现

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

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        // 返回的二维数组
        vector<vector<int>> vec;

        if (root == NULL) {
            return vec;
        }

        // 队列保存树的根节点
        queue<TreeNode*> que;
        // 根节点入队
        que.push(root);
        // 队列为空时，循环结束
        while (!que.empty()) {
            // 用来保存队列中的节点，作为二位数组中的一维数组
            vector<int> v;
            // 临时的队列，用来保存当前出对节点的左右孩子
            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);
                }
                // 队头元素保存至一维数组中
                v.push_back(p->val);
            }
            // 下一层的节点入队
            // 临时队列中的元素进入遍历的队列中
            while (!tmp.empty()) {
                que.push(tmp.front());
                tmp.pop();
            }
            // 一维数组保存至二维数组中
            vec.insert(vec.begin(), v);
        }

        return vec;
    }
};

在代码中，我先让临时队列中的节点进入了要循环遍历的队列中，再把一位数组保存到了二维数组中，这两部的代码顺序是无所谓的。比如可以修改为如下代码：

// 一维数组保存至二维数组中
vec.insert(vec.begin(), v);
// 下一层的节点入队
// 临时队列中的元素进入遍历的队列中
while (!tmp.empty()) {
    que.push(tmp.front());
    tmp.pop();
}

提交结果

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