BAT面试题：请使用递归构建N叉树

题目要求：

现在我们拥有全国的省、市、县、镇的行政信息，比如浙江省 -> 杭州市 -> 西湖区 –> 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=[]}]}

这是我的解答，如果你有更好的解答，欢迎评论分享！