leetcode107.二叉树的层序遍历II

题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

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

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

解答

使用了层次遍历的思想，利用队列实现。具体解题思路如下：

1. 首先定义树的节点结构 TreeNode，包含节点值 val、左子节点指针 left 和右子节点指针 right。
2. 定义一个函数 levelOrderBottom，该函数接受树的根节点 root，并返回层次遍历的结果。
3. 在 levelOrderBottom 函数中，首先创建一个空的二维向量 result，用于保存最终的结果。
4. 若根节点为空，直接返回空的结果向量 result。
5. 创建一个队列 q，将根节点 root 入队。
6. 进入循环，直到队列为空：
   • 获取当前层的节点数量 levelSize，这是为了在遍历当前层时，仅遍历当前层的节点。
   • 创建一个空的向量 level，用于保存当前层的节点值。
   • 进入内层循环，遍历当前层的节点：
     • 取出队首节点 node。
     • 弹出队首节点。
     • 将节点值 node->val 添加到当前层的结果向量 level 中。
     • 若节点的左子节点不为空，将左子节点入队。
     • 若节点的右子节点不为空，将右子节点入队。
   • 将当前层的结果向量 level 插入到结果向量 result 的开头，这是为了保持结果的逆序。
7. 循环结束后，返回结果向量 result。
8. 在 main 函数中，创建一个测试用例 [3,9,20,null,null,15,7] 的树。
9. 调用 levelOrderBottom 函数，获取层次遍历的结果，并输出结果。

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result; // 保存最终的结果
        if (root == NULL) {
            return result;
        }

        queue<TreeNode*> q; // 创建一个队列，用于层次遍历
        q.push(root); // 将根节点入队

        while (!q.empty()) {
            int levelSize = q.size(); // 当前层的节点数量
            vector<int> level; // 保存当前层的节点值

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front(); // 取出队首节点
                q.pop(); // 弹出队首节点
                level.push_back(node->val); // 将节点值保存到当前层的结果中

                if (node->left != NULL) {
                    q.push(node->left); // 将左子节点入队
                }
                if (node->right != NULL) {
                    q.push(node->right); // 将右子节点入队
                }
            }

            result.insert(result.begin(), level); // 将当前层的结果插入到结果向量的开头
        }

        return result;
    }
};