数据对数组构造多叉树

10月15日面试题。

题目

每个数据对，key代表一个节点，value为key节点的一个孩子，给出一个数据对数组，构造出多叉树，返回根节点。
例如，[(1, 2),(1, 3),(1, 4),(2, 5),(2, 6),(3, 7)]
构造的多叉树：

构造的多叉树

解析

1. 依次读取数组每一个数据对，构造两个节点
2. 节点存在一个map结构，当每次解析数据对构造节点时，都先在map中查找是否存在
3. 若节点存在于map中，更新两个节点的关系
4. 若节点不存在与map中，构造节点，更新两个节点的关系
5. 每个节点需要设置一个标记sign字段，用于记录此节点是否为其他节点的子节点
6. 遍历数组构造多叉树完成
7. 对map结构进行遍历，找到节点sign字段标识不是其他节点子节点的节点，这个节点就是根节点

代码

//定义数据对结构
class Pair{
    int k;
    int v;
    public Pair(int k, int v){this.k = k; this.v = v;}
    public int getK() {return k;}
    public int getV() { return v;}
}
//定义多叉树节点结构
class TreeNode{
    int val;
    List<TreeNode> children = new LinkedList<>();//多叉树，节点的孩子节点
    int sign = 0;//0为根节点，1为孩子节点
    public TreeNode(int val){ this.val = val;}
    public int getVal() {return val;}
    public List<TreeNode> getChildren() {return children;}
    public int getSign() {return sign;}
    public void setSign(int sign) {this.sign = sign;}
}
//解析数据对数组，转换为多叉树
public TreeNode convertPairsToTree(Pair[] pairs){
    Map<Integer, TreeNode> map = new HashMap<>();
    //遍历数据对数组
    for (int i = 0; i < pairs.length; ++i){
        //key的节点
        TreeNode kNode = map.get(pairs[i].getK());
        if (null == kNode){
            kNode = new TreeNode(pairs[i].getK());
            map.put(pairs[i].getK(), kNode);
        }
        //value的节点
        TreeNode vNode = map.get(pairs[i].getV());
        if (null == vNode){
            vNode = new TreeNode(pairs[i].getV());
            map.put(pairs[i].getV(), vNode);
        }
        //设置value节点为子节点
        vNode.setSign(1);
        //更新两个节点的父子关系
        kNode.getChildren().add(vNode);
    }
    //对map结构进行遍历，找到节点sign字段标识不是其他节点子节点的节点，这个节点就是根节点
    for (Map.Entry<Integer, TreeNode> entry : map.entrySet()){
        if (entry.getValue().getSign() == 0){
            return entry.getValue();
        }
    }
    return null;
}