We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Java
  3. Advanced
  4. Java Visitor Pattern
  5. Discussions

Java Visitor Pattern

  • KCarot
     + 0 comments

    I have to say that before you submit, you probably won't know that the edge is not pointing from the parent node to the descendant node, and you won't know that the order in which nodes appear is not top-down...

    It seems that several exercises have encountered similar problems in my memory, which has lowered the impression of this website in my mind。

    In the end, it took a lot of time to improve and perfect, and a non recursive tree building process was implemented.Only posted the process of building the tree, by the way, it uses Java8.

    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        int[] values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        Color[] colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);

        int[] edgeCount = new int[n];
        Arrays.fill(edgeCount, 0);
        edgeCount[0] = 1;
        int[] edges = new int[(n - 1) * 2];
        int x, y;
        for (int i = 0; i < edges.length - 1; i += 2) {
            x = sc.nextInt() - 1;
            y = sc.nextInt() - 1;
            edges[i] = x;
            edges[i + 1] = y;

            ++edgeCount[x];
            ++edgeCount[y];
        }

        Tree[] tree = new Tree[n];
        tree[0] = new TreeNode(values[0], colors[0], 0);

        Set<Integer> levelSet = new HashSet<>();
        Set<Integer> tmpSet = new HashSet<>();
        levelSet.add(0);
        while (!levelSet.isEmpty()) {
            for (int i = 0; i < edges.length - 1; i += 2) {
                x = edges[i];
                y = edges[i + 1];
                if (x == -1 || y == -1) {
                    continue;
                }
                if (levelSet.contains(x)) {
                    if (edgeCount[y] > 1) {
                        tree[y] = new TreeNode(values[y], colors[y], tree[x].getDepth() + 1);
                    } else if (edgeCount[y] == 1) {
                        tree[y] = new TreeLeaf(values[y], colors[y], tree[x].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[x]).addChild(tree[y]);
                    tmpSet.add(y);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                } else if (levelSet.contains(y)) {
                    if (edgeCount[x] > 1) {
                        tree[x] = new TreeNode(values[x], colors[x], tree[y].getDepth() + 1);
                    } else if (edgeCount[x] == 1) {
                        tree[x] = new TreeLeaf(values[x], colors[x], tree[y].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[y]).addChild(tree[x]);
                    tmpSet.add(x);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                }
            }
            levelSet.clear();
            levelSet.addAll(tmpSet);
            tmpSet.clear();
        }

        sc.close();
        return tree[0];
    }