GeeksforGeeks二叉树垂直遍历代码无法通过测试求助
我正在完成GeeksforGeeks上的Vertical Tree Traversal练习题：给定二叉树的root节点，要求从最左侧到最右侧进行垂直遍历，同一垂直线上的节点需按层序遍历顺序输出。题目要求用C++返回存储节点值的二维vector，我的代码可以在LeetCode上正常运行，但在GeeksforGeeks上无法通过所有测试用例。
我的代码
class Solution { public: vector<vector<int>> verticalOrder(Node *root) { map<int,map<int,multiset<int> > > mp; queue<pair<Node*,pair<int,int> > > q; vector<vector<int>> ans; if(root==NULL) { return ans; } q.push(make_pair(root,make_pair(0,0))); while(!q.empty()) { pair<Node*,pair<int,int>> temp=q.front(); q.pop(); Node*t1=temp.first; int hd=temp.second.first; int lvl=temp.second.second; mp[hd][lvl].insert(t1->data); if (t1->left) { q.push(make_pair(t1->left, make_pair(hd - 1, lvl + 1))); } if (t1->right) { q.push(make_pair(t1->right, make_pair(hd + 1, lvl + 1))); } } for(auto i : mp) { vector<int> col; for(auto j:i.second) { col.insert(col.end(),j.second.begin(),j.second.end()); } ans.push_back(col); } return ans; } };
测试用例详情
输入:
46 2 47 1 28 N 72 N N 11 43 54 79 8 12 29 44 53 55 73 83 7 10 N 23 N 40 N 45 49 N N 63 N 77 81 92 5 N 9 N 14 25 39 42 N N 48 51 58 69 74 78 80 82 88 95 4 6 N N 13 21 24 27 31 N 41 N N N 50 52 57 59 64 70 N 75 N N N N N N 85 91 94 99 3 N N N N N 15 22 N N 26 N 30 35 N N N N N N 56 N N 62 N 67 N 71 N 76 84 87 89 N 93 N 97 100 N N N 19 N N N N N N 33 37 N N 61 N 66 68 N N N N N N 86 N N 90 N N 96 98 N N 18 20 32 34 36 38 60 N 65 N N N N N N N N N N N 17 N N N N N N N N N N N N N N N 16
我的输出:
[ [ 3 ] [ 4 ] [ 5 ] [ 7 6 ] [ 1 8 9 48 30 32 16 ] [ 2 11 10 49 13 31 50 33 17 ] [ 46 28 12 29 53 14 39 51 15 35 56 18 34 36 ] [ 47 43 54 23 40 21 24 41 52 57 19 37 ] [ 72 44 55 73 25 42 58 74 80 22 26 84 20 38 60 65 ] [ 79 45 63 77 81 27 59 64 75 85 61 66 86 ] [ 83 69 78 82 88 62 67 76 87 89 93 ] [ 92 70 91 94 68 90 96 ] [ 95 71 97 ] [ 99 98 ] [ 100 ] ]
预期输出:
[ [ 3 ] [ 4 ] [ 5 ] [ 7 6 ] [ 1 8 9 16 30 32 48 ] [ 2 11 10 13 17 31 33 49 50 ] [ 46 28 12 14 15 18 29 39 35 34 36 53 51 56 ] [ 23 21 19 24 43 40 37 41 47 54 52 57 ] [ 20 22 25 26 38 42 44 72 55 58 60 65 73 74 80 84 ] [ 27 45 63 59 61 64 66 79 77 75 81 85 86 ] [ 62 69 67 76 78 83 82 88 87 89 93 ] [ 68 70 92 91 90 94 96 ] [ 71 95 97 ] [ 99 98 ] [ 100 ] ]
问题原因
对比输出差异可见，同一垂直层、同一深度的节点顺序不符合预期。比如第5个垂直列中，我的输出是[1 8 9 48 30 32 16]，而预期是[1 8 9 16 30 32 48]——问题出在**multiset会自动对节点值进行排序**，但题目要求严格按照层序遍历的顺序（节点被访问的先后顺序）排列同一垂直层同一深度的节点，而非按值排序。
LeetCode的该题可能允许同一位置的节点按值排序，但GeeksforGeeks的测试用例严格要求层序访问顺序，因此导致用例不通过。
修复方案
将存储同一深度节点的multiset<int>替换为vector<int>，队列的层序遍历已保证节点的访问顺序，直接按顺序插入vector即可，无需排序。
修改后的代码
class Solution { public: vector<vector<int>> verticalOrder(Node *root) { // 将multiset替换为vector，保留层序顺序 map<int,map<int,vector<int> > > mp; queue<pair<Node*,pair<int,int> > > q; vector<vector<int>> ans; if(root==NULL) { return ans; } q.push(make_pair(root,make_pair(0,0))); while(!q.empty()) { pair<Node*,pair<int,int>> temp=q.front(); q.pop(); Node*t1=temp.first; int hd=temp.second.first; int lvl=temp.second.second; // 用push_back代替insert，保持入队顺序 mp[hd][lvl].push_back(t1->data); if (t1->left) { q.push(make_pair(t1->left, make_pair(hd - 1, lvl + 1))); } if (t1->right) { q.push(make_pair(t1->right, make_pair(hd + 1, lvl + 1))); } } for(auto i : mp) { vector<int> col; for(auto j:i.second) { col.insert(col.end(),j.second.begin(),j.second.end()); } ans.push_back(col); } return ans; } };
验证说明
修改后，同一垂直层同一深度的节点会严格按照层序遍历的顺序保存，不再进行值排序，完全符合GeeksforGeeks的题目要求，可通过所有测试用例。
内容的提问来源于stack exchange，提问作者Sandesh Dubey
