题解 | #路径数目#

题意整理

给定一颗有n个节点的树，每个节点的值初始为0或1。
求有多少条从根节点到叶子节点的路径（要求路径上节点值得累加和小于等于2）。

方法一（DFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
从根节点开始递归，并且初始化一个num为2，每到一个节点，num减去对应节点值。如果num小于0，直接终止掉这条路径。否则，遍历当前节点得所有子节点，继续递归，同时判断是否是叶子节点，如果是叶子节点，路径数加一。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 一个整数，表示路径数
     * @param n int 
     * @param Edge Point一维数组 
     * @param f int一维数组 
     * @return int
     */
    //邻接表
    List<List<Integer>> graph;
    //节点个数
    int n;
    //标记数组
    boolean[] v;
    //序列数组
    int[] f;
    //结果变量
    int res;
    public int solve (int n, Point[] Edge, int[] f) {
        //初始化节点个数和邻接表
        this.n=n;
        this.graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //初始化标记数组、序列数组、结果变量
        this.v=new boolean[n];
        v[0]=true;
        this.f=f;
        this.res=0;

        //递归
        dfs(0,2);
        return res;
    }

    private void dfs(int i,int num){
        //如果路径上不止两个值为1，直接返回
        num-=f[i];
        if(num<0) return;
        //看是否是叶子节点
        boolean isLeaf=true;
        for(Integer j:graph.get(i)){
            //遍历未访问的子节点
            if(!v[j]){
                v[j]=true;
                isLeaf=false;
                //往叶子节点递归
                dfs(j,num);
            }
        }
        //如果是叶子节点，res加一
        if(isLeaf){
            res++;
        }
    }
}

3.复杂度分析

时间复杂度：最坏情况下，需要访问所有的节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外深度为n的递归栈、大小为n的标记数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。

方法二（BFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
将根节点入队，累加和初始为2.
每次从队列取出当前节点，累加和减去当前节点的值，遍历当前节点的所有子节点，如果子节点未被访问过，将其打上标记，并将当前节点置为非叶子节点，同时将该子节点入队，继续遍历。如果当前节点是叶子节点，并且累加和大于等于0，说明是满足条件的路劲，将路径数加一。

动图展示：
图片说明

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 一个整数，表示路径数
     * @param n int 
     * @param Edge Point一维数组 
     * @param f int一维数组 
     * @return int
     */
    //邻接表
    List<List<Integer>> graph;
    //节点个数
    int n;
    //标记数组
    boolean[] v;
    //序列数组
    int[] f;
    //结果变量
    int res;
    public int solve (int n, Point[] Edge, int[] f) {
        //初始化节点个数和邻接表
        this.n=n;
        this.graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //初始化标记数组、序列数组、结果变量
        this.v=new boolean[n];
        v[0]=true;
        this.f=f;
        this.res=0;

        //初始化队列
        Queue<int[]> queue=new LinkedList<>();
        //根节点入队，同时节点值累加和初始化为2
        queue.offer(new int[]{0,2});

        while(!queue.isEmpty()){
            int[] node=queue.poll();
            //当前节点和对应累加和
            int i=node[0];
            int num=node[1];
            //减去当前节点值
            num-=f[i];
            boolean isLeaf=true;
            for(Integer j:graph.get(i)){
                //遍历当前节点未访问的子节点
                if(!v[j]){
                    v[j]=true;
                    isLeaf=false;
                    queue.offer(new int[]{j,num});
                }
            }
            //如果是叶子节点，并且num大于等于0，则路径数加一
            if(isLeaf&&num>=0){
                res++;
            }
        }
        return res;
    }

}

3.复杂度分析

时间复杂度：最多访问n个节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外大小为n的队列、大小为n的标记数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。