Department list to tree

import java.util.*;

/**
 * 规律：先序遍历 但是每一层要按照字典序进行
 */
public class Solution {
    /**
     * Convert the department list to preorder traversal of the department tree
     * @param departments string字符串二维数组 [["id1", "parentId", "name"]...], there's only one root department with empty parent id.
     * @return string字符串一维数组
     */
     /**
     * 节点结构
     */
    class Node {
        String id;
        List<Node> sons;
        String name;

        Node(String id, String name) {
            this.id = id;
            this.sons = new ArrayList<>();
            this.name = name;
        }
    }

    List<String> res = new ArrayList<>();

    public String[] listToTree(String[][] departments) {

        System.out.println("z".compareTo("def"));

        //排序 每一层按照字典序进行
        for (int i = 0; i < departments.length; i++) {
            for (int j = i + 1; j < departments.length; j++) {
                if (departments[i][2].compareTo(departments[j][2]) > 0) {
                    String[] temp = departments[i];
                    departments[i] = departments[j];
                    departments[j] = temp;
                }
            }
        }


        //记录父节点
        Deque<String> parents = new ArrayDeque<>();

        //hashMap id Node
        HashMap<String, Node> hashMap = new HashMap<>();
        //超级节点
        hashMap.put("", new Node("", ""));
        //添加节点
        for (int i = 0; i < departments.length; i++) {
            //添加一个节点
            Node n = new Node(departments[i][0], departments[i][2]);
            hashMap.put(departments[i][0], n);
        }
        //添加儿子节点
        for (int i = 0; i < departments.length; i++) {
            //添加一个节点
            hashMap.get(departments[i][1]).sons.add(hashMap.get(departments[i][0]));
        }

        //先序
        preOrder(hashMap, hashMap.get("").sons.get(0).id);

        String[] result = new String[departments.length];

        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }

        return result;
    }

    /**
     * 先序遍历
     *
     * @param hashMap
     * @param curNodeId
     */
    public void preOrder(HashMap<String, Node> hashMap, String curNodeId) {

        res.add(hashMap.get(curNodeId).name);
        if (hashMap.get(curNodeId).sons.size() == 0) {
            return;
        }
        for (Node n : hashMap.get(curNodeId).sons) {
            preOrder(hashMap, n.id);
        }

    }
}

class TreeNode:
    def __init__(self, ID, name):
        self.ID = ID
        self.name = name
        self.children = []
class Solution:
    def listToTree(self , departments ):
        # write code here
        node_dict = {}
        for de in departments:
            node = TreeNode(de[0], de[2])
            node_dict[de[0]] = node
            if de[1] == '':
                root = node
        for de in departments:
            if de[1] != '':
                node = node_dict[de[1]]
                node.children.append(node_dict[de[0]])
        result = [root.name]
        def preorder(tree_node):
            if tree_node is None:
                return
            for child in sorted(tree_node.children, key=lambda x:x.name):
                result.append(child.name)
                preorder(child)
        preorder(root)
        return result
import json
input_ = json.loads(input())
result = Solution().listToTree(input_)
result = str(result).replace('\'','\"')
result = result.replace('\", ','\",')
print(result)

import java.util.*;
 
 
public class Solution {
    /**
     * Convert the department list to preorder traversal of the department tree
     * @param departments string字符串二维数组 [["id1", "parentId", "name"]...], there's only one root department with empty parent id.
     * @return string字符串一维数组
     */
    int index = 0;
    public String[] listToTree (String[][] departments) {
        // write code here
        Map<String,List<String>> map = new HashMap<>();
        Map<String,String> nameMapper = new HashMap<>();
        for(int i = 0;i < departments.length;i++){
            String id = departments[i][0];
            String parentId = departments[i][1];
            String name = departments[i][2];
            if(map.get(parentId) == null){
                List<String> tmp = new ArrayList<>();
                map.put(parentId,tmp);
            }
            if(map.get(id) == null){
                List<String> tmp = new ArrayList<>();
                map.put(id,tmp);
            }
            map.get(parentId).add(id);
            nameMapper.put(id,name);
        }
        int len = departments.length;
        String[] ans = new String[len];
        dfs(map.get("").get(0),map,nameMapper,ans);
        return ans;
    }
    void dfs(String cur,Map<String,List<String>> map,Map<String,String> nameMapper,String[] ans){
        ans[index++] = nameMapper.get(cur);
        List<String> list = new ArrayList<>();
        for(int i = 0;i < map.get(cur).size();i++){
            String id = map.get(cur).get(i);
            list.add(id);
        }
        Collections.sort(list,(st1,st2)->{
            String cur1 = nameMapper.get(st1);
            String cur2 = nameMapper.get(st2);
            for(int i = 0;i < Math.min(cur1.length(),cur2.length());i++){
                if(cur1.charAt(i) != cur2.charAt(i)){
                    return cur1.charAt(i) - cur2.charAt(i);
                }
            }
            return cur1.length() - cur2.length();
        });
        for(int i = 0;i < list.size();i++){
            dfs(list.get(i),map,nameMapper,ans);
        }
        return;
    }
}

import queue
class Node:
    def __init__(self,id:str, name:str) :
        self.id = id
        self.sons = []
        self.name = name
    


class Solution :
   

    res = []

    def listToTree(self,departments) :



        
        for  i in range(len(departments)):
            for j in range(i + 1,len( departments)):
                if departments[i][2] > departments[j][2] :
                    temp = departments[i]
                    departments[i] = departments[j]
                    departments[j] = temp


       
        parents = queue.Queue()

    
        hashMap = dict()
        
       
        hashMap[""] =  Node("", "")
      
        for i in range(len( departments)):
      
            hashMap[departments[i][0]] = Node(departments[i][0], departments[i][2])
        

        for i in range(len( departments)):
    
            hashMap.get(departments[i][1]).sons.append(hashMap.get(departments[i][0]))


        self.preOrder(hashMap, hashMap.get("").sons[0].id)

        result = []

        for i in range(len( self.res)):
            result.append(self.res[i])
        

        return result
    


    def preOrder(self,hashMap:dict, curNodeId:str):

        self.res.append(hashMap.get(curNodeId).name);
        if len(hashMap.get(curNodeId).sons) == 0 :
            return
        
        for n in hashMap.get(curNodeId).sons :
            self.preOrder(hashMap, n.id)

departmentsColLen是一个不需要的参数，而本题也表意不明，ColLen确定是3了却给出一个变量，折腾了半天。

      /**
     * N叉树前序遍历的非递归实现
     * @param departments
     * @return 先序遍历序列
     */
    public String[] listToTree (String[][] departments) {
        
        // 建立ID与Name的映射关系
        Map<String, String> idNameMap = new HashMap<String, String>();
        for (int i = 0; i < departments.length; i++) {
            idNameMap.put(departments[i][0],departments[i][2]);
        }
        
        // 用邻接表存储树形结构 由于部门名称唯一 故可将部门名称作为Key
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        String root = null;
        for (int i = 0; i < departments.length; i++) {
            if (map.containsKey(idNameMap.get(departments[i][1]))) {
                map.get(idNameMap.get(departments[i][1])).add(idNameMap.get(departments[i][0]));
            }else {
                if (!departments[i][1].equals("")) {
                    ArrayList<String> list = new ArrayList<String>();
                    list.add(idNameMap.get(departments[i][0]));
                    map.put(idNameMap.get(departments[i][1]), list);
                }
                
                if (departments[i][1].equals("")) {
                    root = idNameMap.get(departments[i][0]);
                }
            }    
        }
        
        // 利用栈实现N叉树前序遍历的非递归
        String[] result = new String[departments.length];
        LinkedList<String> stack = new LinkedList<String>();
        
        stack.push(root);
        int index = 0;
        ArrayList<String> list = null;
        while (! stack.isEmpty()) {
            String currentNode = stack.pop();
            result[index++] = currentNode; // 访问当前节点

            if (map.get(currentNode) != null) { // 当前节点有孩子节点
                list = map.get(currentNode);
                Collections.sort(list); // 按字典排序
                for (int i = list.size() - 1; i >= 0; i--) {  // 注意这里安排字典序的倒序插入栈中
                    stack.push(list.get(i));
                }
            }    
        }
        
        return result;
    }