利用邻接表进行图的深度搜索

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.ArrayList;

public class Main {
    static boolean[] visited;   // 标记节点是否已经被访问
    static int[] weight;        // 节点权值
    static int[] childNum;      // 存储以节点i为根的树有多少个节点
    static int[] max, min;      // 存储以节点i为根的子树下的最大值和最小值
    // 节点间的最大差值
    static int maxDiff = -1;
    // 待求节点
    static int node = -1;
    // 邻接表
    static HashMap<Integer, ArrayList<Integer>> tree;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().trim().split(" ");
        int n = Integer.parseInt(temp[0]);
        int k = Integer.parseInt(temp[1]);
        temp = br.readLine().trim().split(" ");
        weight = new int[n + 1];
        for(int i = 1; i <= n; i++) weight[i] = Integer.parseInt(temp[i - 1]);
        int x, y;
        // 构建树图的邻接表
        tree = new HashMap<>();
        ArrayList<Integer> list;
        for(int i = 1; i <= n - 1; i++){
            temp = br.readLine().trim().split(" ");
            x = Integer.parseInt(temp[0]);
            y = Integer.parseInt(temp[1]);
            if(tree.containsKey(x)){
                list = tree.get(x);
                list.add(y);
                tree.put(x, list);
            }else{
                list = new ArrayList<>();
                list.add(y);
                tree.put(x, list);
            }
            if(tree.containsKey(y)){
                list = tree.get(y);
                list.add(x);
                tree.put(y, list);
            }else{
                list = new ArrayList<>();
                list.add(x);
                tree.put(y, list);
            }
        }
        int root = Integer.parseInt(br.readLine().trim());
        visited = new boolean[n + 1];
        max = new int[n + 1];
        min = new int[n + 1];
        childNum = new int[n + 1];
        dfs(root, k);
        System.out.println(node);
    }
    //求取parent下面的最值
    public static void dfs(int parent, int k){
         visited[parent] = true;
        // 初始化parent下的最值为parent的节点权重
        max[parent] = weight[parent];
        min[parent] = weight[parent];
        // 初始情况下，该子树只有一个节点
        childNum[parent] = 1;
        for(int i = 0; i < tree.get(parent).size(); i++){
            int child = tree.get(parent).get(i);
            if(!visited[child]){
                // 没访问过这个孩子节点就进行深搜
                dfs(child, k);
                max[parent] = Math.max(max[parent], max[child]);
                min[parent] = Math.min(min[parent], min[child]);
                childNum[parent] += childNum[child];
            }
        }
        if(childNum[parent] <= k && max[parent] - min[parent] >= maxDiff){
            // 以parent为根节点的子树满足节点数小于等于k，且最大差值大于等于目前最大
            if(max[parent] - min[parent] > maxDiff){
                // 大于了直接更新，等于的话需要考虑哪个根节点的编号小
                node = parent;
                maxDiff = max[parent] - min[parent];
            }else{
                // 如果node还没有赋值，就直接赋值为当前节点，否则取满足要求的节点中编号最小的
                node = node == -1? parent: Math.min(node, parent);
            }
    }
}
}

总结

图的DFS：

• 必须有个邻接表HashMap<Integer, ArrayList<Integer>>来记录相邻节点的关系，或者是矩阵。
• 标记数组
• 在限定条件下去进性深度优先搜索，再去更新一些我们要求的值