【图论树深度优先搜索】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

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛