【图论 树 深度优先搜索】2246. 相邻字符不同的最长路径

本文涉及知识点

图论 树

图论知识汇总
深度优先搜索汇总

LeetCode 2246. 相邻字符不同的最长路径

给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。
另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。
示例 1：
输入：parent = [-1,0,0,1,1,2], s = “abacbe”
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。
示例 2：
输入：parent = [-1,0,0,0], s = “aabc”
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：
n == parent.length == s.length
1 <= n <= 10⁵
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

深度优先搜索

令根节点的深度为0，其它节点的深度为父节点深度+1。
枚举各路径的最小深度节点。
DFS(cur)返回 cur 符合以下条件的最长路径长度：
一，cur是深度最小的节点。
二，cur是起点（终点）。
v = {1,1}
如果s[child] != s[cur]，1 + DFS(child)加到v。
返回值就是v的最大值。
最小深度为cur的最长路径为：v的最大两个值-1。
** 时间复杂度** ： O(nlongn)，每个节点处理一次，子节点的结果排序。
** 注意** ：s[child]==s[cur]是 DFS要执行，要枚举cur作为最小深度的路径。
用 map或堆代码v，如果元素数量超过2就删除，时间复杂度可以为：O(n)。

代码

核心代码

template<class ELE, class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft, (ELE)other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	int longestPath(vector<int>& parent, string s) {
		m_s = s;
		const int N = parent.size();
		vector<vector<int>> vNeiBo(N);
		int root = -1;
		for (int i = 0; i < parent.size(); i++) {
			if (-1 == parent[i]) {
				root = i;
			}
			else {
				vNeiBo[parent[i]].emplace_back(i);
			}
		}
		DFS(vNeiBo, root);
		return m_iRet;
	}
	int DFS(const vector<vector<int>>& vNeiBo, int cur) {
		vector<int> v = { 1,1 };
		for (const auto& child : vNeiBo[cur]) {
			if (m_s[cur] == m_s[child]) {
				DFS(vNeiBo,child); 
				continue; }
			v.emplace_back(DFS(vNeiBo, child) + 1);
		}
		sort(v.begin(), v.end(), std::greater<>());
		MaxSelf(&m_iRet, v[0] + v[1] - 1);
		return v[0];
	}
	int m_iRet = 1;
	string m_s;
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}



namespace UnitTest
{
	vector<int> parent;
	string s;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod01)
		{
			parent = { -1, 0, 0, 1, 1, 2 }, s = "abacbe";
			auto res = Solution().longestPath(parent, s);
			AssertEx(3, res);
		}
	
		TEST_METHOD(TestMethod02)
		{
			parent = { -1, 0, 0, 0 }, s = "aabc";
			auto res = Solution().longestPath(parent, s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod03)
		{
			parent = { -1, 0, 1 }, s = "aab";
			auto res = Solution().longestPath(parent, s);
			AssertEx(2, res);
		}
	};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。