Leetcode 429: N叉树的层次遍历

2022-04-08 约 400 字预计阅读 1 分钟 - 次阅读

22年4月8日的每日一题，很简单的BFS层次遍历树。唯一的问题在于对BFS的细节理解不到位，我的做法与标准做法相比多开了一个map来保存节点的高度信息。实际上完全不用在意这个高度信息，直接每次BFS完之后就一定是新的一层。

我的做法：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        // 从根节点开始进行BFS
        // 对于每一个新的点，计算其层次并进行记录
        // 对于每一个进入的节点，判断其层次。如果层次相同，则放在相同的数组内；如果层次不同，则另外申请一个数组
        queue<Node*> bfs_queue;
        map<Node*,int> high;
        vector<vector<int>> result;

        int current_high = 0; // 0 层，同时也对应着索引0
        if(root==nullptr){
            return result;
        }
        high[root] = 0;
        result.emplace_back(vector<int>{});
        bfs_queue.push(root);
        while(!bfs_queue.empty()){
            Node* cur_node = bfs_queue.front(); bfs_queue.pop();
            if(cur_node == nullptr){
                continue;
            }
            // judge new
            if(high[cur_node] > current_high){
                current_high += 1;
                result.emplace_back(vector<int>{});
            }
            result[current_high].push_back(cur_node->val);

            // bfs
            for(auto next_node : cur_node->children){
                high[next_node] = current_high + 1;
                bfs_queue.push(next_node);
            }
        }
        return result;
    }
};

标准做法：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root) {
            return {};
        }

        vector<vector<int>> ans;
        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            int cnt = q.size();
            vector<int> level;
            for (int i = 0; i < cnt; ++i) {
                Node* cur = q.front();
                q.pop();
                level.push_back(cur->val);
                for (Node* child: cur->children) {
                    q.push(child);
                }
            }
            ans.push_back(move(level));
        }

        return ans;
    }
};