image.png

思路：BFS + map

  • 首先，每个节点都有一个自己的位置参数cur_pos，就是通过这个参数分类节点，初始的root节点的位置参数是0，后面的节点，左边则LC314.二叉树的垂直遍历 - 图2，右边则LC314.二叉树的垂直遍历 - 图3
  • 常规的做法是使用队列来进行BFS，这里采用for循环去遍历数组，也是可以的，因为nodes.size()是动态更新的，空间消耗大一点，其他倒是差不多
  • 利用map自动排序，边BFS边往数组里面插入，最后得到结果image.png

    代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> verticalOrder(TreeNode* root) {
  15.         vector<vector<int>> vert_seq;
  16.         if (!root) {
  17.             return vert_seq;
  18.         }
  20.         // 第二个参数表示偏移的坐标
  21.         vector<pair<TreeNode*, int>> nodes;
  22.         nodes.push_back({root, 0});
  24.         map<int, vector<int>> map_pos;
  25.         for (int i = 0; i < nodes.size(); i++) {
  26.             pair<TreeNode*, int> cur_node = nodes[i];
  27.             int cur_pos = cur_node.second;
  29.             // 插入map当中, 利用map实现自动排序
  30.             map_pos[cur_pos].push_back(cur_node.first->val);
  31.             if (cur_node.first->left) {
  32.                 nodes.push_back({cur_node.first->left, cur_pos - 1});
  33.             }
  34.             if (cur_node.first->right) {
  35.                 nodes.push_back({cur_node.first->right, cur_pos + 1});
  36.             }
  37.         }
  39.         // map to vector
  40.         for (map<int, vector<int>>::iterator it = map_pos.begin(); it != map_pos.end(); ++it) {
  41.             vert_seq.push_back(it->second);
  42.         }
  44.         return vert_seq;
  45.     }
  46. };