LeetCode 314. 二叉树的垂直遍历（BFS/DFS）

示例 1：
输入: [3,9,20,null,null,15,7]

   3
  /\
 /  \
9   20
    /\
   /  \
  15   7 

输出:
[
  [9],
  [3,15],
  [20],
  [7]
]

示例 2:
输入: [3,9,8,4,0,1,7]

     3
    /\
   /  \
  9    8
  /\   /\
 /  \ /  \
4   0 1   7 

输出:
[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

示例 3:
输入: [3,9,8,4,0,1,7,null,null,null,2,5]
（注意：0 的右侧子节点为 2，1 的左侧子节点为 5）

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

输出:
[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

class Solution {
	map<int, vector<pair<int,int>>> ans;
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for(auto& a : ans)
        {	//按横坐标取出
        	sort(a.second.begin(), a.second.end(),[&](auto a, auto b){
                return a.first < b.first;//按深度排序
            });
            vector<int> temp;
            for(auto& d_val : a.second)
                temp.push_back(d_val.second);
        	res.push_back(temp);
        }
        return res;
    }
    void dfs(TreeNode* root, int x, int deep)
    {
    	if(!root) return;
    	ans[x].push_back({deep, root->val});//深度、val
    	dfs(root->left, x-1, deep+1);
    	dfs(root->right, x+1, deep+1);
    }
};

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
    	if(!root) return {};
        vector<vector<int>> res;
        map<int,vector<int>> m;
        queue<pair<TreeNode*,int>> q;
        int size, x, val;
        TreeNode *cur;
        q.push({root, 0});
        while(!q.empty())
        {
        	size = q.size();
        	while(size--)
        	{
                cur = q.front().first;
        		val = cur->val;
        		x = q.front().second;
                q.pop();
        		m[x].push_back(val);
        		if(cur->left)
        			q.push({cur->left, x-1});
        		if(cur->right)
        			q.push({cur->right, x+1});
        	}
        }
        for(auto& mi : m)
            res.push_back(mi.second);
        return res;
    }
};