102.二叉树的层次遍历 (Medium)*

题目描述*

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

示例*

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

返回其层次遍历结果：

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

代码*

如果仅是层次遍历序列，用一个队列就行，但是这个要求分层，可以用来两个队列交替使用。或者可以把内层换成 for 循环，次数为队列长度，以控制一次仅访问同一层。当然也可以用 dfs，填一个 depth 参数即可。

双队列for 循环

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> helpQueue;
        queue<TreeNode*> helpQueue2;
        vector<vector<int>> res;
        if(root == nullptr) {
            return res;
        }
        vector<int> tmp;
        TreeNode *cur = root;
        helpQueue.push(root);
        while(!helpQueue.empty() || !helpQueue2.empty()) {
            while(!helpQueue.empty()) {
                cur = helpQueue.front();
                tmp.push_back(cur->val);
                helpQueue.pop();
                if(cur->left != nullptr) {
                    helpQueue2.push(cur->left);
                }
                if(cur->right != nullptr) {
                    helpQueue2.push(cur->right);
                }
            }
            if(tmp.size()) {
                res.push_back(tmp);
                tmp.clear();
            }
            while(!helpQueue2.empty()) {
                cur = helpQueue2.front();
                tmp.push_back(cur->val);
                helpQueue2.pop();
                if(cur->left != nullptr) {
                    helpQueue.push(cur->left);
                }
                if(cur->right != nullptr) {
                    helpQueue.push(cur->right);
                }
            }
            if(tmp.size()) {
                res.push_back(tmp);
                tmp.clear();
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(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 times = helpQueue.size();
            for(int i = 0; i < times; 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);
                }
            }
            if(tmp.size()) {
                res.push_back(tmp);
                tmp.clear();
            }
        }
        return res;
    }
};

最后更新: July 23, 2022