相邻字符不同的最长路径

相邻字符不同的最长路径,第1张

题目
给你一棵 树(即一个连通、无向、无环图),根节点是节点 0 ,这棵树由编号从 0 到 n - 1 的 n 个节点组成。

用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树,其中 parent[i] 是节点 i 的父节点,由于节点 0 是根节点,所以 parent[0] == -1 。

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-path-with-different-adjacent-characters

思路

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

代码

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;          // 返回半径

    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/674958.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表(0条)

保存