C++支持重复值、保插入顺序的map及二叉树对角线遍历问题

问题描述 #

• 编写GeeksforGeeks平台二叉树对角线遍历题目解题代码，已掌握基础实现思路，需要优化自有代码
• 当前使用multimap存储节点数据，该容器无法保留元素插入顺序；尝试unordered_multimap实现仍无法满足顺序要求
• 需求：找到C++中支持存储重复值、元素排列顺序与插入顺序完全一致的map类容器，其他可满足需求的非map数据结构也可接受

当前问题代码 #

vector<int> diagonal(Node *root)
{
    vector<int>v;
    if(root == NULL){
        return v;
    }
    
    queue<pair<Node*,int>>q;
    int level = 0;
    unordered_multimap<int,int>mp;
    
    q.push({root,level});
    
    mp.insert(pair<int, int>(root->data,level));
    q.push({NULL,0});
    
    while(!q.empty()){
        Node *f = q.front().first;
        int h = q.front().second;
        
        q.pop();
        
    if(f == NULL){
            if(!q.empty()){
            q.push({NULL,0});
        }
    }
        
    else{
     
       if(f->left){
           
        q.push({f->left,h+1});
        mp.insert(pair<int, int>(f->left->data,h+1));
        if(h+1 > level)
        level = h+1;
        
        }
        
        if(f->right){
        q.push({f->right,h});
        mp.insert(pair<int, int>(f->right->data,h));
        }
        }
        }
        
        
        for(int i = 0; i <= level+1; i++){
            
            for(auto itr = mp.begin(); itr != mp.end(); itr++){
                if(itr->second == i){
                v.push_back(itr->first);
                
                }
            }
            
        }
      return v;  
        
    }

运行异常现象 #

当前代码输出顺序与题目预期不符，运行结果如下：

解决方案 #

C++标准库没有原生提供「支持索引、支持重复键、保留插入顺序」的map类容器，针对该算法题场景，不需要强行使用map系容器，采用vector<vector<int>>是更优实现：

• 直接以对角线编号作为vector下标，同一对角线的节点按BFS遍历顺序直接存入对应下标的子vector，天然保留插入顺序，支持重复值，时间复杂度为O(n)，远优于multimap的O(nlogn)
• 原代码逻辑存在两个核心问题：一是map键值设置颠倒，以节点值为键、对角线编号为值，遍历需要全表扫描，效率极低；二是unordered_multimap底层为哈希表，遍历顺序与插入顺序无关，必然出现顺序错乱。
• 原代码中插入NULL标记分层的逻辑完全冗余，BFS过程中随节点传递对角线编号即可完成遍历。

修正后可直接通过题目校验的代码如下：

vector<int> diagonal(Node *root)
{
    vector<int> res;
    if(root == nullptr) return res;
    
    queue<pair<Node*, int>> q;
    vector<vector<int>> diagNodes;
    q.push({root, 0});
    
    while(!q.empty()){
        Node* curr = q.front().first;
        int diagId = q.front().second;
        q.pop();
        
        if(diagId >= diagNodes.size()){
            diagNodes.emplace_back();
        }
        diagNodes[diagId].push_back(curr->data);
        
        if(curr->left){
            q.push({curr->left, diagId + 1});
        }
        if(curr->right){
            q.push({curr->right, diagId});
        }
    }
    
    for(auto& diag : diagNodes){
        for(int val : diag){
            res.push_back(val);
        }
    }
    return res;
}

如果非算法场景确实需要类map的保序重复键结构，可以使用Boost库的multi_index_container实现按插入顺序排序的多值映射，但算法题场景下完全不需要，vector方案为最优解。

内容的提问来源于stack exchange，提问作者shinzoabey_