相邻字符不同的最长路径

题目 给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

思路

二叉树的最大直径问题 双亲表示法变为邻接表 后序遍历 注意函数每次返回的是半径，计算的是直径

代码

class Solution {
          
   
public:
    int ans=0;
    int longestPath(vector<int>& parent, string s) {
          
   

        // 二叉树的最大直径问题
        // 双亲表示法变为邻接表
        // 后序遍历
        // 注意函数每次返回的是半径，计算的是直径

        unordered_map<int,vector<int>> mp;

        for(int i=0;i<parent.size();i++)
        mp[parent[i]].push_back(i);                // 邻接表

        postOrderTraverse(mp,0,s);

        return ans;
        
    }

    int postOrderTraverse(unordered_map<int,vector<int>>& mp,int root,string& s){
          
   

        if(mp[root].size()==0){
          
   
        ans=max(ans,1);
        return 1;
        }

        int max_num=1;
        int max_dep=0;

        priority_queue<int,vector<int>,less<int>> q;

        for(int i=0;i<mp[root].size();i++){
          
   

            int t=postOrderTraverse(mp,mp[root][i],s);

            if(s[root]!=s[mp[root][i]]){
          
   
                q.push(t);
                max_dep=max(max_dep,t);
            }
        }

        if(q.size()>=1){
          
   
            max_num+=q.top();
            q.pop();
        }

        if(q.size()>=1){
          
   
            max_num+=q.top();
            q.pop();
        }

        ans=max(ans,max_num);        // 计算直径

        return max_dep+1;          // 返回半径

    }
};