二叉树的垂序遍历

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree

数据范围

树中结点数目总数在范围 [1, 1000] 内

0 <= Node.val <= 1000

示例一

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：

• 列 -1 ：只有结点 9 在此列中。
• 列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
• 列 1 ：只有结点 20 在此列中。
• 列 2 ：只有结点 7 在此列中。

示例二

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：

• 列 -2 ：只有结点 4 在此列中。
• 列 -1 ：只有结点 2 在此列中。
• 列 0 ：结点 1 、5 和 6 都在此列中。

      1 在上面，所以它出现在前面。
      5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
  

• 列 1 ：只有结点 3 在此列中。
• 列 2 ：只有结点 7 在此列中。

思路

题意大概是将二叉树上的value以一定顺序排列
每一列排列在一起，考虑层序层序相同的再考虑值序 ！

所以这题本质上就是遍历二叉树，让符合条件的value排入到数组中

AC代码

class Solution {
public:
    map<int,multiset<int>> mp;
    void xswl(TreeNode* p,int x,int y)
    {
        if(p == nullptr) return ;
        mp[x].insert(y * 100000 + p->val); // 确保每一层的value在同一层的是按大小排列的
        xswl(p->left,x-1,y+1);
        xswl(p->right,x+1,y+1);
        return ;
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> ans;
        xswl(root,0,0);
        for(auto i: mp){
            vector<int> temp;
            for(auto j:i.second) temp.push_back(j % 100000);
            ans.push_back(temp);
        }
        return ans;
    }
};