107. 二叉树的层序遍历 II

算法内容

本文件实现 LeetCode 107「二叉树的层序遍历 II」。核心思路是先按普通层序遍历从上到下收集每一层节点值，再对结果整体反转，得到自底向上的层序结果。

实现中使用两个队列：s 保存当前层待访问节点，tmp_s 暂存下一层节点。当前层队列清空时，将本层结果写入 res，再把下一层队列转为当前层继续处理。最后通过 reverse(res.begin(), res.end()) 将层序结果倒置。时间复杂度为 O(n)，每个节点访问一次；空间复杂度为 O(n)，主要来自队列和结果数组。

算法实现

/**
 * 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) {}
 * };
 */
  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) {}
 };
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> s;
        if(root != nullptr) {
            s.push(root);
        }
        vector<vector<int>> res;
        vector<int> tmp;
        queue<TreeNode*> tmp_s;
        while(!s.empty()) {
            tmp.push_back(s.front()->val);
            TreeNode* tmp_node = s.front();
            if(tmp_node->left != nullptr) {
                tmp_s.push(tmp_node->left);
                // printf("add %d\n", tmp_node->left->val);
            }
            if(tmp_node->right != nullptr) {
                tmp_s.push(tmp_node->right);
                // printf("add %d\n", tmp_node->right->val);
            }
            s.pop();
            if(s.empty() && !tmp_s.empty()) {
                res.push_back(tmp);
                tmp.clear();
                while (!tmp_s.empty()){
                    s.push(tmp_s.front());
                    tmp_s.pop();
                }
            }
        }
        if(!tmp.empty()) {
            res.push_back(tmp);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};