java类似stl建树代码（ACM）

java实现stl建树的方法，就是类似于c++那样，创建一个list数组，将元素压入到指定的list[x]中

在dfs函数中可以进行调用，实现遍历这个树

list数组建树：

import java.util.*;
public class Main{
    static List[] list=new ArrayList[100005];
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n=cin.nextInt();
        for(int i=0;i<=n;i++) list[i]=new ArrayList();
        for(int i=1;i<n;i++){
            int x=cin.nextInt();
            int y=cin.nextInt();
            list[x].add(y);list[y].add(x);      //两边压入
        }
        dfs(1,0);
    }
    static void dfs(int d,int pre){     //d是顶点，pre是父点
        System.out.println(d);
        int l=list[d].size();
        for(int i=0;i<l;i++){
            int son=(int)list[d].get(i);
            if(son!=pre){       //不为父点则进入
                dfs(son,d);
            }
        }
    }
}
/*
4
1 2
2 3
2 4
*/

同c++，二维list并不能很好实现树的建立，需要提前压入多个list后才可。

但是java的二维list可能真不行，因为非数组形式的二维list无法继续压入

即数组形式可实现：list[x].add(10)

二维形式要这样：list.get(x).add(10)

可以看到get函数返回的不是可改的对象，是一个仅可读的对象，没有listx]的指针不能进行压入。

java建树的方法还有map建树：

主要就是类似于c++的map<int,vector<int>> mp；去映射一个序列，没有上面好用仅做了解即可

map = new HashMap<>();
for(int i = 1; i <= N; i++) map.put(i, new ArrayList<>());        //指定下标压入一个序列

import java.util.*;

//某树形DP题代码

public class Main{
    static int[] h;
    static Map<Integer, List<Integer>> map;
    static int[][] f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        h = new int[N + 1];
        map = new HashMap<>();
        int root = (N + 1) * N / 2;
        for(int i = 1; i <= N; i++) map.put(i, new ArrayList<>());
        for(int i = 1; i <= N; i++) h[i] = sc.nextInt();
        for(int i = 1; i <= N - 1; i++){
            int l = sc.nextInt(), k = sc.nextInt();
            root -= l;
            map.get(k).add(l);
        }
        f = new int[N + 1][2];
        dfs(root);
        System.out.println(Math.max(f[root][0], f[root][1]));
    }
    static void dfs(int x){
        f[x][1] = h[x];
        for(int son: map.get(x)){
            dfs(son);
            f[x][0] += Math.max(f[son][0], f[son][1]);
            f[x][1] += f[son][0];
        }
    }
}