九章演算法 | Hulu 面試題：Print Organization Chart

來自專欄九章演算法 - LintCode領扣 題解4 人贊了文章

撰文 | JZ

專欄 | 九章演算法

題目描述

按員工姓名，上一級姓名，職位，年份給出一系列企業中員工的關係，輸出企業成員組織結構圖。

思路點撥

按員工關係表建立一棵樹，然後先序遍歷這棵樹，注意樹的每一層要進行排序。

考點分析

本題主要考察了樹的構造與樹的遍歷，首先根據每位員工上一級的信息構造出樹結構，再對這顆樹進行先序遍歷，即可以得到答案，值得注意的是每一級員工要按名字的字典序進行排序。

九章參考程序

https://www.jiuzhang.com/solution/print-organization-chart

/*** 本參考程序來自九章演算法，由 @華助教 提供。版權所有，轉發請註明出處。* - 九章演算法致力於幫助更多中國人找到好的工作，教師團隊均來自矽谷和國內的一線大公司在職工程師。* - 現有的面試培訓課程包括：九章演算法班，系統設計班，演算法強化班，Java入門與基礎演算法班，Android 項目實戰班，* - Big Data 項目實戰班，演算法面試高頻題班, 動態規劃專題班* - 更多詳情請見官方網站：http://www.jiuzhang.com/?source=code*/ public class Solution { /** * @param relationship: the relationship * @return: the organization chart */ List<List<Integer>> graph; List<String> nameList; List<String> ans; HashMap<String, Integer> nameMap; void dfs(int x, int depth, List<List<String>> relationship) { String ins = ""; for (int i = 0; i < depth; i++) { ins = ins + "-"; } ins = ins + relationship.get(x).get(0) + " (" + relationship.get(x).get(2) + ") " + relationship.get(x).get(3); ans.add(ins); for (int i = 0; i < graph.get(x).size(); i++) { dfs(graph.get(x).get(i), depth + 1, relationship); } } class Cmp implements Comparator<Integer> { public int compare(Integer a, Integer b) { return nameList.get(a).compareTo(nameList.get(b)); } } public List<String> getOrganization(List<List<String>> relationship) { // Write your code here nameList = new ArrayList<String>(); for (int i = 0; i < relationship.size(); i++) { nameList.add(relationship.get(i).get(0)); } int root = 0; graph = new ArrayList<List<Integer>>(); nameMap = new HashMap<String, Integer>(); for (int i = 0; i < relationship.size(); i++) { graph.add(new ArrayList<Integer>()); } for (int i = 0; i < relationship.size(); i++) { if (relationship.get(i).get(1).equals("NULL")) { root = i; } nameMap.put(relationship.get(i).get(0), i); } for (int i = 0; i < relationship.size(); i++) { if (!relationship.get(i).get(1).equals("NULL")) { int x = nameMap.get(relationship.get(i).get(0)); int y = nameMap.get(relationship.get(i).get(1)); graph.get(y).add(x); } } for (int i = 0; i < graph.size(); i++) { Collections.sort(graph.get(i), new Cmp()); } ans = new ArrayList<String>(); dfs(root, 0, relationship); return ans; }}

推薦閱讀：