二叉树的层序遍历 II（queue+reverse）1

二叉树的层序遍历 II 是一个典型的二叉树问题，主要涉及数据结构中的队列和算法中的深度优先搜索（DFS）或广度优先搜索（BFS）。在这个问题中，我们需要实现一种特殊形式的层序遍历，即从底层的叶子节点开始，逐层向上遍历，直至根节点。具体来说，给定一个二叉树的根节点，返回自底向上的层序遍历结果。 我们来看一下给定的二叉树节点定义： ```cpp 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) {} }; ``` 这是一个简单的二叉树节点结构，包含一个整数值 `val` 和两个指向左右子节点的指针 `left` 和 `right`。另外，还提供了三种构造函数方便创建节点。 接下来，我们看具体的解决方案，这里采用的是广度优先搜索（BFS）策略： ```cpp class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> res; // 存储结果的二维数组 queue<TreeNode*> q; // 使用队列存储当前层的节点 // 将根节点入队 if (root) { q.push(root); } // 当队列不为空时，进行遍历 while (!q.empty()) { int row = q.size(); // 当前层的节点数量 vector<int> tmp; // 存储当前层的节点值 // 遍历当前层的所有节点 while (row--) { TreeNode* cur = q.front(); q.pop(); tmp.push_back(cur->val); // 将左右子节点入队，如果存在的话 if (cur->left) { q.push(cur->left); } if (cur->right) { q.push(cur->right); } } // 将当前层的节点值添加到结果中 res.push_back(tmp); } // 将结果反转，得到自底向上的顺序 reverse(res.begin(), res.end()); return res; } }; ``` 这个解决方案的核心在于使用广度优先搜索（BFS）。将根节点放入队列。然后，每次从队列中取出一层的节点，将其值存入一个临时数组 `tmp`，并将它们的子节点（如果有的话）加入队列。重复这个过程，直到队列为空，即所有节点都被处理过。由于我们要自底向上返回结果，所以需要对存储结果的二维数组 `res` 进行反转。 在二叉树的层序遍历 II 中，关键在于理解自底向上的含义，并正确地利用队列来实现这一遍历方式。这个问题可以扩展到其他类似的问题，比如二叉树的其他遍历方式，或者在遍历过程中执行特定操作。熟悉并掌握这种遍历方法对于解决其他二叉树问题非常有帮助。