树的所有路径问题

Question

问一个算法题

有这样的一个结构

找出所有可能的路径
规则：
1、每个节点深度优先查找child每一项的内容然后依次拼接
2、每个节点查找完child后再去找next，next可能有多项，每一次只能走一项
3、直到最后的节点没有next为止
4、child下可能有next，也可能child的每一项还会有child和next
其中child是数组,next是对象

例1：

let root={
    id:1,
    child:[
        {
            id:7,
            child:{},
            next:{}
        },
        {
            id:2,
            child:{},
            next:{}
        }
    ],
    next:{
        3:{
            id:3,
            child:[
                {
                    id:5,
                    child:[],
                    next:{}
                }
            ]
        },
        4:{
            id:4,
            child:[
                {
                    id:6,
                    child:[],
                    next:{}
                }
            ]
        }
    }
}

所有可能路径为：
[1,7,2,3,5]
[1,7,2,4,6]

因为3，4在next里，要么走3，要么走4

例2：

let root={
    id:1,
    child:[{
        id:11,
        child:[{
            id:12,
            child:[],
            next:{}
        }],
        next:{
            13:{
                id:13,
                child:[],
                next:{}
            },
            14:{
                id:14,
                child:[],
                next:{}
            }
        }
    }],
    next:{
        2:{
            id:2,
            next:{
                8:{
                    id:8,
                    child:[],
                    next:{}
                }
            },
            child:[{
                id:5,
                next:{},
                child:{}
            },{
                id:6,
                next:{
                    7:{
                        id:7,
                        next:{},
                        child:[]
                    }
                },
                child:{}
            }]
        },
        3:{
            child:[
                {
                    id:9,
                    child:[],
                    next:{}
                },
                {
                    id:10,
                    child:[],
                    next:{}
                }
            ],
            next:{}
        }
    }
}

结果为：
[1,11,12,13,2,5,6,7,8]
[1,11,12,13,3,9,10]
[1,11,12,14,2,5,6,7,8]
[1,11,12,14,3,9,10]

Answer 1

先深搜压缩数据，记录所有的前后驱关系。
再根据关系表深搜所有可能的结果。

import java.util.*;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, List<Integer>> next = new HashMap<>();

    public List<List<Integer>> solve(Data data) {
        dfs_link(data, Collections.emptyList());
        dfs(data.getId(), new ArrayList<>());
        return ans;
    }

    /**
     * 填充next表
     *
     * @param data 当前递归的节点
     * @param prev 上一个访问的节点
     * @return 当前节点组成的数组中最后一个节点的所有可能值
     */
    private List<Integer> dfs_link(Data data, List<Integer> prev) {
        prev.forEach(p -> next.computeIfAbsent(p, e -> new ArrayList<>()).add(data.getId()));
        List<Integer> now = Collections.singletonList(data.getId());
        for (Data d : data.getChild()) {
            now = dfs_link(d, now);
        }
        if (data.getNext().isEmpty()) return now;
        List<Integer> res = new ArrayList<>();
        for (Data d : data.getNext().values()) {
            res.addAll(dfs_link(d, now));
        }
        return res;
    }

    /**
     * 根据前后驱关系表遍历节点
     *
     * @param id  当前递归的节点
     * @param res 结果数组
     */
    private void dfs(Integer id, List<Integer> res) {
        res.add(id);
        if (next.containsKey(id)) {
            next.get(id).forEach(d -> dfs(d, new ArrayList<>(res)));
        } else {
            ans.add(res);
        }
    }
}