生物进化录

/*
 * 题目思路：
 * 首先构建树形结构，并对其进行深度优先遍历。
 * 我们需要记录每个节点的子节点，并确保我们始终以字典序最小的方式记录遍历路径。
 * 每次遇到一个节点时，先记录'0'，表示访问该节点，然后访问其所有子节点，最后记录'1'，表示返回父节点。
 */
import java.util.*;
import java.util.stream.Collectors;

public class EvolutionTreeStream {
    public String getEvolutionSequence(int[] parents) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < parents.length; i++) {
            tree.computeIfAbsent(parents[i], k -> new ArrayList<>()).add(i);
        }
        StringBuilder sb = new StringBuilder();
        dfs(0, tree, sb);
        return sb.toString();
    }

    private void dfs(int node, Map<Integer, List<Integer>> tree, StringBuilder sb) {
        sb.append('0'); // 记录当前节点
        if (tree.containsKey(node)) {
            tree.get(node).stream()
                .sorted() // 确保以字典序遍历
                .forEach(child -> dfs(child, tree, sb));
        }
        sb.append('1'); // 返回到父节点
    }

    public static void main(String[] args) {
        EvolutionTreeStream et = new EvolutionTreeStream();
        int[] parents1 = {-1, 0, 0, 2};
        System.out.println(et.getEvolutionSequence(parents1)); // 输出: 00110

        int[] parents2 = {-1, 0, 0, 1, 2, 2};
        System.out.println(et.getEvolutionSequence(parents2)); // 输出: 00101100
    }
}