BFS by Java (Explained)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe number of target nodes is calculated by adding the number of target nodes on the or
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe number of target nodes is calculated by adding the number of target nodes on the original tree and the number of target nodes after connecting another tree. As the 2 trees are independent, we could calculate these 2 numbers seperately.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use adjacent lists to describe the graphs\n2. Find the number of target nodes for each node on 2 trees\n        - Tree1: the number of edges on the path $u$ to $v$ is no larger than k (We need number for each node, the result should be store in an array)\n        - Tree2: the number of edges on the path $u$ to $v$ is no larger than k-1 (We only need the maximum value, the result is only an integer)\n3. Add the number from Tree2 to each number in Tree1\n\n# Complexity\n- Time complexity: $$O(N_1 + N_2+K)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N_1 + N_2)$$ where $N_1$ is the length of $edges1$ and $N_2$ is the length of $edges2$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {\n        int n1 = edges1.length+1; \n        int[] result = new int[n1];\n        \n        // if k equals to 0, we could not connect 2 trees together and every node has the only one target node, which is itself.\n        if (k == 0) {\n            Arrays.fill(result, 1);\n            return result;\n        }\n\n        // find the adjacent list of each node in 2 trees\n        List<List<Integer>> adj1 = adjcentList(edges1);\n        List<List<Integer>> adj2 = adjcentList(edges2);\n        \n        // for the first tree, find the number of target nodes for each node\n        for(int i=0; i<n1; i++) {\n            result[i] = bfs(adj1, k, i);\n        }\n\n        int n2 = edges2.length+1;\n        int maxValue = 0;\n        // we only need the node that has the maximum number of targer nodes for the second tree\n        for(int i=0; i<n2; i++) {\n            // as we need 1 edge to connect 2 trees, \n            maxValue = Math.max(bfs(adj2, k-1, i), maxValue);\n        }\n\n        // add the maximum number of target nodes from the second tree to each node on the first tree\n        for(int i=0; i<n1; i++) {\n            result[i] += maxValue;\n        }\n        \n        return result;\n    }\n\n    private List<List<Integer>> adjcentList(int[][] edges1) {\n        List<List<Integer>> adj = new ArrayList<>();\n        int n = edges1.length+1;\n        for(int i=0; i<n; i++) {\n            adj.add(new ArrayList<>());\n        }\n        // add edges to both nodes\n        for(int[] edges: edges1) {\n            adj.get(edges[0]).add(edges[1]);\n            adj.get(edges[1]).add(edges[0]);\n        }\n        return adj;\n    }\n\n    // return the number of target nodes\n    private int bfs(List<List<Integer>> adj, int k, int i) {\n        Queue<Integer> queue = new LinkedList<>();\n        boolean[] visited = new boolean[adj.size()];\n        queue.offer(i);\n        int temp = k;\n        int result = 1;\n        // The number of nodes is smaller than k\n        while (temp-- > 0) {\n            int size = queue.size();\n            for(int j=0; j<size; j++) {\n                int curr = queue.poll();\n                // mark the visited nodes\n                visited[curr] = true;\n                for(int num: adj.get(curr)) {\n                    // if the child nodes are unvistied, we add it to the queue\n                    if (!visited[num]) {\n                        queue.offer(num);\n                    }\n                }\n            }\n            result += queue.size();\n        }\n        return result;\n    }\n}\n```
['Breadth-First Search', 'Queue', 'Java']