题解 | #Department list to tree#

列表每一个条目第一个字符串是当前部门id,第二个字符串是父节点（父部门）id,第三个字符串是部门名称。
主要思想：
1.建立父节点id到其所有子节点的映射（子节点集合set有序，而且是字典序。
2.建立部门名称到部门id的映射。
3.找到根节点。
4.从根节点递归先序遍历。

class Solution {
    unordered_map<string, set<string>>ump;//无序map 有序set, 每个id的子节点 set
    unordered_map<string, string> umps;//部门名字 id 映射
public:
    vector<string> listToTree(string** departments, int departmentsRowLen, int* departmentsColLen) {
        string root;//根节点
        for(int i=0;i<departmentsRowLen;i++){ 
            umps[departments[i][2]]=departments[i][0];//建立部门名字到部门id的映射"                     
            if(departments[i][1]==""){//root节点没有父节点  
                root=departments[i][2];//根节点名字
            }else ump[departments[i][1]].insert(departments[i][2]);// key:父节点id。value:孩子节点 部门名字set 
        } 
         vector<string> res;//结果
         preOrder(root,res);//先序遍历root
         return res;
    }
    void preOrder(string& root, vector<string>& res){
        res.push_back(root);//先添加当前节点
        set<string> children=ump[umps[root]];//根据id获取当前节点所有子节点，set已按字典有序
        for(auto child: children) preOrder(child, res);//递归先序遍历每个子节点
    }
};