Leetcode-987 (二叉树的垂序遍历)

 1 #define pb push_back
 2 class Solution
 3 {
 4     public:
 5         vector<vector<int> > verticalTraversal(TreeNode* root)
 6         {
 7             
 8             vector<vector<int>> rnt;
 9             if(!root)
10                 return rnt;
11             
12             vector<vector<vector<int>>> v(1000,vector<vector<int>>(1000));
13             queue<pair<pair<int,int>,TreeNode*>> q;
14             q.push({{0,501},root});
15             
16             while (!q.empty())
17             {
18                 auto a = q.front();
19                 q.pop();
20                 v[a.first.first][a.first.second].pb(a.second->val);
21                 if (a.second->left)
22                     q.push({{a.first.first+1,a.first.second-1}, a.second->left});
23                 if (a.second->right)
24                     q.push({{a.first.first+1,a.first.second+1}, a.second->right});
25             }
26             
27             for(int j = 0;j < 1000;j ++)
28             {
29                 vector<int> vTmp;
30                 for(int i = 0;i < 1000;i ++)
31                 {
32                     if(!v[i][j].empty())
33                     {
34                         sort(v[i][j].begin(),v[i][j].end());
35                         for(int k = 0;k < v[i][j].size();k ++)
36                         {
37                             vTmp.pb(v[i][j][k]);
38                         }
39                     }
40                 }
41                 if(!vTmp.empty())
42                 rnt.pb(vTmp);
43             }
44             return rnt;
45         }
46 };