Sponsored
Sponsored
This approach uses Depth First Search (DFS) to explore the tree and find the longest path with different adjacent characters. The idea is to recursively explore each node, keeping track of the longest path encountered. As you traverse, ensure that any subsequent node is only considered in the path if it has a different character from its parent.
Time Complexity: O(n).
Space Complexity: O(n) due to the storage of the children array.
The code defines a DFS function that explores each node's children, calculates the longest path from its children nodes that have distinct characters compared to the node. It accumulates the longest paths and returns the overall result.
Instead of using recursion, consider using an iterative Breadth First Search (BFS) approach. In this scenario, you explore each node level by level, maintaining a similar mechanism for avoiding paths with identical adjacent characters.
This approach generally requires additional bookkeeping to manage the nodes and their path lengths, but it can be beneficial in scenarios where recursion depth potential is problematic or not desired.
Time Complexity: O(n^2) in this version due to lack of adjacency list optimization.
Space Complexity: O(n) related to queue usage.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#define MAX_NODES 100000
5
6typedef struct {
7 int node;
8 int length;
9} QueueItem;
10
11static int bfs(int parent[], int n, char s[]) {
12 int maxLen = 1;
13 QueueItem queue[MAX_NODES];
14 int front = 0, rear = 0;
15 queue[rear++] = (QueueItem){0, 1}; // Starting from root
16
17 while (front < rear) {
18 QueueItem item = queue[front++];
19 int node = item.node;
20 int length = item.length;
21
22 for (int i = 0; i < n; i++) {
23 if (parent[i] == node && s[node] != s[i]) {
24 queue[rear++] = (QueueItem){i, length + 1};
25 if (length + 1 > maxLen) {
26 maxLen = length + 1;
27 }
28 }
29 }
30 }
31 return maxLen;
32}
33
34int longestPath(int* parent, int parentSize, char* s) {
35 return bfs(parent, parentSize, s);
36}This implementation uses a queue-based BFS approach instead of recursion. Each node and its path length are enqueued, and the traversal occurs iteratively. As children are explored, they are enqueued only if their character differs from their parent.