107.二叉树的层次遍历 II (Easy)*

题目描述*

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

示例*

给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

代码*

这次是要自底向上的层次遍历，可以用之前的 bfs，每次在 res 开头插入。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> helpQueue;
        vector<vector<int>> res;
        vector<int> tmp;
        if(root == nullptr) {
            return res;
        }
        helpQueue.push(root);
        TreeNode *cur = root;
        while(!helpQueue.empty()) {
            int len = helpQueue.size();
            for(int i = 0; i < len; i++) {
                cur = helpQueue.front();
                tmp.push_back(cur->val);
                helpQueue.pop();
                if(cur->left != nullptr) {
                    helpQueue.push(cur->left);
                }
                if(cur->right != nullptr) {
                    helpQueue.push(cur->right);
                }
            }
            res.insert(res.begin(), tmp);
            tmp.clear();
        }
        return res;
    }
};

最后更新: July 23, 2022