[LeetCode] 102. 二叉树的层序遍历

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

示例 1：

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

输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

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

思路:

基本的树操作，可以用队列暂存一下节点访问

AC代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;  
        queue<TreeNode*> nodeQueue;              
        vector<int> level;
        int size,i;  
        TreeNode* current;  
          
        if(root == NULL) return result;  
        nodeQueue.push(root); 
        while(!nodeQueue.empty()) {   
            level.clear();  
            size = nodeQueue.size();  
            for(i=0; i < size; i++) {  
                current = nodeQueue.front();
                nodeQueue.pop(); 
                level.push_back(current->val);  
                if(current->left) {  
                    nodeQueue.push(current->left);  
                }  
                if(current->right) {  
                    nodeQueue.push(current->right);  
                }  
            }  
            result.push_back(level); 
        }  
        return result;  
    }
};Code language: C++ (cpp)

稍快一些的做法是:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        
        queue<TreeNode*> nodeQueue{{root}};
        
        while (!nodeQueue.empty()) {
            res.emplace_back();       // 直接添加空vector，原地构造
            for (int i = nodeQueue.size(); i > 0; --i) {
                auto node = nodeQueue.front(); nodeQueue.pop();
                res.back().push_back(node->val);
                if (node->left)  nodeQueue.push(node->left);
                if (node->right) nodeQueue.push(node->right);
            }
        }
        return res;
    }
};Code language: C++ (cpp)