3373. Maximize the Number of Target Nodes After Connecting Trees II
Approach
Color both trees bipartite; pick larger color class from tree2; combine with tree1 same-parity nodes.
Key Techniques
Tree problems typically require recursive DFS or iterative BFS. Common patterns: preorder for serialization, inorder for BST sorted output, postorder for bottom-up aggregation. Always consider edge cases: null nodes, single-node trees, and skewed (list-like) trees.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: Color both trees bipartite; pick larger color class from tree2; combine with tree1 same-parity nodes.
// Time: O(n + m) Space: O(n + m)
public class Solution
{
public int[] MaxTargetNodes(int[][] edges1, int[][] edges2)
{
int n = edges1.Length + 1;
int m = edges2.Length + 1;
List<int>[] graph1 = BuildGraph(edges1, n);
List<int>[] graph2 = BuildGraph(edges2, m);
bool[] parity1 = new bool[n];
bool[] parity2 = new bool[m]; // Placeholder (not used)
int even1 = Dfs(graph1, 0, -1, parity1, true);
int even2 = Dfs(graph2, 0, -1, parity2, true);
int odd1 = n - even1;
int odd2 = m - even2;
int[] ans = new int[n];
for (int i = 0; i < n; i++)
{
int tree1 = parity1[i] ? even1 : odd1;
// Can connect the current node in tree1 to either an even or an odd node
// in tree2.
int tree2 = Math.Max(even2, odd2);
ans[i] = tree1 + tree2;
}
return ans;
}
// Returns the number of nodes that can be reached from u with even steps.
private int Dfs(List<int>[] graph, int u, int prev, bool[] parity, bool isEven)
{
int res = isEven ? 1 : 0;
parity[u] = isEven;
foreach (int v in graph[u])
{
if (v != prev)
res += Dfs(graph, v, u, parity, !isEven);
}
return res;
}
private List<int>[] BuildGraph(int[][] edges, int n)
{
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++)
graph[i] = new List<int>();
foreach (int[] edge in edges)
{
int u = edge[0];
int v = edge[1];
graph[u].Add(v);
graph[v].Add(u);
}
return graph;
}
}