美团秋招第五场Q2：二叉树相似节点的对数

做了半天愣是0%，发帖记录

（Java）

节点类：
class Node {
    int val;
    List neighbor = new ArrayList<>();
    boolean visited;
}

思路：
1. 先获取到所有边，存到节点数组中；
2. 已知根节点为“1”，使用广度优先或者层式遍历方式遍历；
3. 遍历时注意判断当前节点的neighbor是否已被访问（即为父节点），排除父节点后则可知子节点数量；

代码实践：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

class Node {
    int val;
    List neighbor = new ArrayList<>();

    public Node(int val) {
        this.val = val;
    }
}

public class T2 {
    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int T = in.nextInt();
        int T = 1;
        int[] ns = new int[]{7};
        int[][] bs = new int[][]{
                {1, 2},
                {1, 3},
                {3, 5},
                {3, 7},
                {2, 4},
                {2, 6}
        };

        for (int i = 0; i < T; i++) {
            long res = 0;
//            int n = in.nextInt();
            int n = ns[i];

            Node[] nodeArr = new Node[n];

            for (int j = 0; j < n - 1; j++) {
                int u = bs[j][0];
                int v = bs[j][1];

                if (nodeArr[u - 1] == null) {
                    nodeArr[u - 1] = new Node(u - 1);
                }
                if (nodeArr[v - 1] == null) {
                    nodeArr[v - 1] = new Node(v - 1);
                }
                nodeArr[u - 1].neighbor.add(nodeArr[v - 1]);
                nodeArr[v - 1].neighbor.add(nodeArr[u - 1]);
            }

            int[] count = new int[3];

            count[nodeArr[0].neighbor.size()]++;
            Set visited = new HashSet<>();
            visited.add(nodeArr[0].val);

            List curNodes = nodeArr[0].neighbor;
            List tmpNodes = new ArrayList<>();

while (curNodes.size() > 0) {
                for (Node node : curNodes) {
                    visited.add(node.val);
                    List nextNodes = node.neighbor.stream().filter(nodeTmp -> !visited.contains(nodeTmp.val)).collect(Collectors.toList());
                    int childNum = nextNodes.size();
                    count[childNum]++;
                    tmpNodes.addAll(nextNodes);
                }
                curNodes = tmpNodes;
                tmpNodes = new ArrayList<>();
            }
            for (int c: count) {
                res += getPairCount(c);
            }
            System.out.println(res);
        }
    }

    static long getPairCount(int n) {
        if (n <= 1) {
            return 0;
        }
        return (long) n * (n - 1) / 2;
    }
}

全部评论

推荐最新楼层