前言

這篇文章承接了之前的文章，都是關於面試的內容。作者是我的一個學弟，目前是大三，所以他的文章偏重於實習/校招。因此有相關經歷的小夥伴如果想認識他，可以後台私信我。

這是他的其他一些文章：

面試阿里前，問問自己能不能手寫這道題

面試被問到Spring IOC、AOP和動態代理，用這篇文章懟過去

面試被問到Java虛擬機，用這篇文章懟過去

正文

題目要求：

現在我們擁有全國的省、市、縣、鎮的行政信息，比如 浙江省 -> 杭州市 -> 西湖區 –> 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=[]}]}

這是我的解答，如果你有更好的解答，歡迎評論分享！