题目描述

给出一颗以1为根的树，树上节点的值只为1或者0，在最多经过两个值为1的节点的情况下，有多少条到达叶节点的路径？
输入
第一个参数为 n ，(1≤n≤100,000)
第二个参数为大小为 n-1 的点对 的集合，其中 表示结点 ui 与结点 vi之间有一条边， ,
第三个参数为大小为 n 的 0/1 序列 f ， 为i-1结点的值。
返回
一个整数，表示路径数
示例1
输入：7,[(7,2),(6,1),(5,2),(1,2),(4,6),(6,3)],[0,0,1,0,1,0,0]
返回值：4
说明：样例中的四条路径分别为: (1 - 2 - 7), (1 - 2 - 5) , (1 - 6 - 3), (1 - 6 - 4)
图片说明

题目分析

题目与“NC614”类似，都是给出了n-1条边，通过构建邻接表来表示树结构，然后再对树进行遍历得到想要的结果；
邻接表主要是对每个结点都创建一个存储相邻的结点的列表，在列表中会重复记录父节点，所以需要一个访问数组 visited 来标记结点是否已经被访问过，第一次遇到说明是父节点，会继续遍历它的邻接表，后面再次遇到说明是子节点的邻接点，可以跳过；
题目要求的在最多经过两个值为1的节点的情况下，可以直接将经过的结点值相加，若路径和小于等于2即满足要求；
图片说明

解题思路

方法1：创建邻接表表示树信息，使用dfs遍历树
dfs的思路比较直观：
1.创建邻接表graph，根据Edge数组初始化邻接表；
2.创建访问数组 visited 来标记结点是否已经访问过；
3.dfs从根开始遍历，访问根的子节点（邻接表），在访问的结点中若没有子节点，则说明是叶子结点，同时使用一个sum统计路过的叶子结点的值和，当sum<=2时，res加1；

方法2：创建邻接表表示树信息，使用bfs遍历树
bfs遍历树，一般借助队列来实现，在这里的队列不仅要记录树结点，还需要记录经过的结点和，所以在队列中存放一个长度为2的数组array，array[0]表示树结点，array[1]表示从根节点到当前结点的路径和，判断是否是叶子结点与dfs相似，满足叶子结点和array[1]<=2，res加1。

代码实现

方法1：dfs遍历

    // 邻接表
    List<List<Integer>> graph = new ArrayList<>();
    int res = 0;
    public int solve (int n, Point[] Edge, int[] f) {
        // write code here
        // 初始化邻接表
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<Edge.length;i++){
            int u = Edge[i].x-1;
            int v = Edge[i].y-1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        // 定义访问数组
        boolean[] visited = new boolean[n];
        // 从根节点开始遍历
        visited[0] = true;
        dfs(0, visited, f, f[0]);
        return res;
    }

    public void dfs(int i, boolean[] visited, int[] f, int sum){
        // 已经超过限制，直接返回
        if(sum > 2) return;
        // 从根节点遍历到叶子结点
        List<Integer> list = graph.get(i);
        // 标记是否为叶子结点
        boolean isLeaf = true;
        for(Integer child:list){
            if(!visited[child]){
                visited[child] = true;
                isLeaf = false;
                dfs(child, visited, f, sum+f[child]);
            }
        }
        if(isLeaf){
            res++;
        }
    }

时间复杂度：，首先需要创建长度为n的邻接表，同时也要遍历Edge数组，在dfs的过程中，在每个结点都只有一个子节点的情况下，递归深度达到最大n，所以花费的总时间是n级别；
空间复杂度：，空间上需要2(n-1)来存邻接结点（n个结点的树有n-1条边，边上的两个结点都会在邻接表中重复出现，所以是2(n-1)），还需要深度最大为n的递归栈空间；

方法2：bfs遍历

    // 邻接表
    List<List<Integer>> graph = new ArrayList<>();
    int res = 0;
    public int solve (int n, Point[] Edge, int[] f) {
        // write code here
        // 初始化邻接表
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<Edge.length;i++){
            int u = Edge[i].x-1;
            int v = Edge[i].y-1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        // 定义访问数组
        boolean[] visited = new boolean[n];
        // 从根节点开始遍历
        visited[0] = true;
        // 借助队列实现bfs
        Queue<int[]> queue = new LinkedList<>();
        // 存储的信息是：结点+当前路径上经过的结点和
        queue.offer(new int[]{0, 0});
        while(!queue.isEmpty()){
            // 获取结点
            int[] node = queue.poll();
            int i = node[0];
            int sum = node[1];
            // 路径和要加上遍历到的i结点的值
            sum += f[i];
            boolean isLeaf = true;
            for(Integer child:graph.get(i)){
                if(!visited[child]){
                    visited[child] = true;
                    // 存在子节点则不是叶子结点
                    isLeaf = false;
                    // 将子节点和子节点路径和加入队列
                    queue.offer(new int[]{child, sum});
                }
            }
            if(isLeaf && sum <= 2){
                // 到了叶子结点，且路径和小于2，符合条件
                res++;
            }
        }
        return res;
    }

时间复杂度：，与dfs类似需要遍历数组，bfs使用的队列，省掉了递归的栈时间，增加了遍历邻接表的时间，时间复杂度为n级别；
空间复杂度：，与dfs相似，减少了栈空间，增加了队列来存储结点值，空间复杂度级别为n。