HOT100 102二叉树的层序遍历

2023-04-07

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路

二叉树的层序遍历比较常规，即用队列存储待遍历的节点，某个节点出队后，将它的左右孩子入队，重复这个操作，直到队列为空。

这个题的不同之处在于需要将遍历结果存放到vector<vector>中，每一层的节点值放到一个vector中，并层层压入vector<vector>，因此需要额外维护一个值用来标记当前节点属于哪一层，因此可以在队列中用pair存放节点及其标记。

代码

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<pair<TreeNode*,int>> nodeQ;
        vector<vector<int>> result;
        if(root==nullptr){
            return result;
        }
        //先把根节点放进去
        pair<TreeNode*,int>a;
        a.first=root;
        a.second=1;
        nodeQ.push(a);
        vector<int> level;
        int sign=1;
        while(!nodeQ.empty()){
            pair<TreeNode*,int> temp=nodeQ.front();
            if(temp.second==sign){
                level.push_back(temp.first->val);
                nodeQ.pop();
                if(temp.first->left!=nullptr){
                    pair<TreeNode*,int> k;
                    k.first=temp.first->left;
                    k.second=temp.second+1;
                    nodeQ.push(k);
                }
                if(temp.first->right!=nullptr){
                    pair<TreeNode*,int> k;
                    k.first=temp.first->right;
                    k.second=temp.second+1;
                    nodeQ.push(k);
                }
            }else{
                sign++;
                result.push_back(level);
                level.clear();
                level.push_back(temp.first->val);
                nodeQ.pop();
                if(temp.first->left!=nullptr){
                    pair<TreeNode*,int> k;
                    k.first=temp.first->left;
                    k.second=temp.second+1;
                    nodeQ.push(k);
                }
                if(temp.first->right!=nullptr){
                    pair<TreeNode*,int> k;
                    k.first=temp.first->right;
                    k.second=temp.second+1;
                    nodeQ.push(k);
                }
            }
        }
        result.push_back(level);
        return result;
    }
};

执行用时：4 ms, 在所有 C++ 提交中击败了69.39%的用户
内存消耗：12.2 MB, 在所有 C++ 提交中击败了60.92%的用户
通过测试用例：34 / 34

评论