尋夢新聞LINE@每日推播熱門推薦文章，趣聞不漏接❤️
前言
這篇文章承接了之前的文章，都是關於面試的內容。作者是我的一個學弟，目前是大三，所以他的文章偏重於實習/校招。因此有相關經歷的小夥伴如果想認識他，可以後台私信我。
這是他的其他一些文章：
面試被問到Spring IOC、AOP和動態代理，用這篇文章懟過去
正文
題目要求：
現在我們擁有全國的省、市、縣、鎮的行政信息，比如 浙江省 -> 杭州市 -> 西湖區 –> xx街道，請將這些信息構建成一棵樹，根節點為全國，葉子節點為鎮。
我的誤解：
剛開始我並沒有明白題意，走了彎路，只是簡單的構建了一個多叉樹。代碼如下：
import java.util.ArrayList;
import java.util.List;
public class SiteTree {
public final static String COUNTRY = "國";
public final static String PROVINCE = "省";
public final static String CITY = "市";
private static class Node {
private String level; //國》省》市》縣》鎮
private String name; //例如：山東省、濟南市等具體地名
private List<Node> child; //下一級節點列表
private Node(String level, String name) {
this.level = level;
this.name = name;
}
//Getter Setter
}
public static void main(String[] args) {
//聲明一個根節點
Node GUO = new Node(SiteTree.COUNTRY, "中國");
//山東省下的市級單位
Node JINAN = new Node(SiteTree.CITY, "濟南市");
Node JINING = new Node(SiteTree.CITY, "濟寧市");
//將市級節點放入山東省級節點下
Node QLU = new Node(SiteTree.PROVINCE, "山東省");
SiteTree.add(QLU, JINAN, JINING);
//將省級節點放入國級節點下
Node ZJS = new Node(SiteTree.PROVINCE, "浙江省");
SiteTree.add(GUO, QLU, ZJS);
//不再舉例...
System.out.println(GUO);
}
public static void add(Node parent, Node... child) {
List<Node> childs = new ArrayList<>();
for (int i = 0; i < child.length; i++) {
childs.add(child[i]);
}
parent.setChild(childs);
}
}
當面試官看到代碼後，提示我：你需要做到一個通用的方法。我沒太明白，面試官又說：主要考察你對遞歸的使用。
看到這里，我忽然明白了面試官的意圖：使用遞歸去構建N叉樹。
擺在我面前的一個問題是，我該如何去讀取數據源，數據源儲存的形式是什麼？是文本文件還是數據庫？
文本文件說實話，不太好做到，而且不規範，正常邏輯數據應該儲存在數據庫。
但是我現在總不能去裝個數據庫吧？再寫DAO層查詢接口？這不現實。
沒辦法，只能自己簡單模擬下數據庫操作了！
表結構都是一行一行的數據，那就用List。每行數據（節點）不能只有主鍵，還要有父節點的外鍵，因為題目要求也給出了數據是具有指向關係的 。
如何做到數據的查詢呢？當然是用Stream，最簡單。
分析到這里，完整的代碼已經呼之欲出，請看大螢幕 ↘
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class SiteTree {
public final static String COUNTRY = "國";
public final static String PROVINCE = "省";
public final static String CITY = "市";
private static List<Node> list = initData();
//結合數據庫比較好做到，所以簡單做到下！
private static class Node{
private int cid; //節點ID
private int pid; //父節點ID
private String level; //國》省》市》縣》鎮
private String name; //例如：山東省、濟南市等具體地名
private List<Node> child = new ArrayList<>(); //下一級節點列表
public Node(int cid, int pid, String level, String name) {
this.cid = cid;
this.pid = pid;
this.level = level;
this.name = name;
}
public int getCid() {
return cid;
}
public int getPid() {
return pid;
}
public String getName() {
return name;
}
public List<Node> getChild() {
return child;
}
@Override
public String toString() {
return "Node{" +
"cid=" + cid +
", pid=" + pid +
", level='" + level + '\'' +
", name='" + name + '\'' +
", child=" + child +
'}';
}
}
/**
* 初始化數據庫
* @return
*/
private static List<Node> initData() {
//聲明一個根節點
Node GUO = new Node(1,0,SiteTree.COUNTRY,"中國");
//將市級節點放入山東省級節點下
Node QLU = new Node(4,1,SiteTree.PROVINCE, "山東省");
//將省級節點放入國級節點下
Node ZJS = new Node(5,1,SiteTree.PROVINCE,"浙江省");
//山東省下的市級單位
Node JINAN = new Node(2,4,SiteTree.CITY,"濟南市");
Node JINING = new Node(3,4,SiteTree.CITY,"濟寧市");
//簡單數據庫做到
List<Node> list = new ArrayList<>();
list.add(GUO);
list.add(JINAN);
list.add(JINING);
list.add(QLU);
list.add(ZJS);
return list;
}
public static void main(String[] args){
System.out.println(child(1));
}
private static Node child(int cid) {
//獲取節點
Node node = getTreeNode(cid);
//獲取子節點
List<Node> childNodes = getChildNode(cid);
//遍歷子節點
for (Node child : childNodes){
Node n = child(child.getCid());//遞歸
node.getChild().add(n);
}
return node;
}
private static Node getTreeNode(int cid) {
return list.stream().filter(node -> {
if (node.getCid() == cid) {
return true;
}
return false;
}).findFirst().get();
}
private static List<Node> getChildNode(int pid) {
return list.stream().filter(node -> {
if (node.getPid() == pid) {
return true;
}
return false;
}).collect(Collectors.toList());
}
}
列印輸出：
Node{cid=1, pid=0, level='國', name='中國', child=[
Node{cid=4, pid=1, level='省', name='山東省', child=[
Node{cid=2, pid=4, level='市', name='濟南市', child=[]},
Node{cid=3, pid=4, level='市', name='濟寧市', child=[]}]},
Node{cid=5, pid=1, level='省', name='浙江省', child=[]}]}
這是我的解答，如果你有更好的解答，歡迎評論分享！
