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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int dfs(int node, const string &s, vector<vector<int>> &children, int &max_length) {
9 int first_longest = 0, second_longest = 0;
10 for (int child : children[node]) {
11 int current_length = dfs(child, s, children, max_length);
12 if (s[node] != s[child]) {
13 if (current_length > first_longest) {
14 second_longest = first_longest;
15 first_longest = current_length;
16 } else if (current_length > second_longest) {
17 second_longest = current_length;
18 }
19 }
20 }
21 max_length = max(max_length, first_longest + second_longest + 1);
22 return first_longest + 1;
23 }
24
25 int longestPath(vector<int>& parent, string s) {
26 int n = parent.size();
27 vector<vector<int>> children(n);
28 for (int i = 1; i < n; ++i) {
29 children[parent[i]].push_back(i);
30 }
31 int max_length = 0;
32 dfs(0, s, children, max_length);
33 return max_length;
34 }
35};The solution uses DFS to traverse the tree structure by maintaining a list of children for each node. The longest unique character path is calculated for each node using recursion.
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.
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.