本文涉及知识点

C++图论 换根法
C++DFS
C++BFS算法

LeetCode2385. 感染二叉树需要的总时间

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
每分钟，如果节点满足以下全部条件，就会被感染：
节点此前还没有感染。
节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
示例 1：
输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：

• 第 0 分钟：节点 3
• 第 1 分钟：节点 1、10、6
• 第 2 分钟：节点5
• 第 3 分钟：节点 4
• 第 4 分钟：节点 9 和 2
  感染整棵树需要 4 分钟，所以返回 4 。
  示例 2：
  输入：root = [1], start = 1
  输出：0
  解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
  提示：
  树中节点的数目在范围 [1, 10⁵] 内
  1 <= Node.val <= 10⁵
  每个节点的值 互不相同
  树中必定存在值为 start 的节点

DFS+换根法+图论

DFS遍历整个二叉树，建立临接表。以start为根，求各节点的层次。最大层次就是结果，start是0层。

代码

class CBFSLeve {
public :
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	template<class NextFun>
	static vector<int> Leve(int N,NextFun nextFun, vector<int> start) {
		vector<int> leves(N, -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			auto nexts = nextFun(start[i]);
			for (const auto& next : nexts) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	static vector<vector<int>> LeveNodes(const vector<int>& leves) {
		const int iMaxLeve = *max_element(leves.begin(), leves.end());
		vector<vector<int>> ret(iMaxLeve + 1);
		for (int i = 0; i < leves.size(); i++) {
			ret[leves[i]].emplace_back(i);
		}
		return ret;
	};
};

class Solution {
		public:
			int amountOfTime(TreeNode* root, int start) {
				const int N = 100'000;
				vector<vector<int>> neiBo(N + 1);
				function<void(TreeNode*, TreeNode*)> DFS = [&](TreeNode* par, TreeNode* cur) {
					if ((nullptr != par) && (nullptr != cur)) {
						neiBo[par->val].emplace_back(cur->val);
						neiBo[cur->val].emplace_back(par->val);
					}
					if (nullptr != cur) {
						DFS(cur, cur->left);
						DFS(cur, cur->right);
					}
				};
				DFS(nullptr, root);
				auto leves = CBFSLeve::Leve(neiBo, { start });
				return *max_element(leves.begin(), leves.end());
			}
		};

单元测试

vector<int> nums;
		int start;
		const int null = 10000;
		TEST_METHOD(TestMethod1)
		{
			nums = { 1, 5, 3, null, 4, 10, 6, 9, 2 }, start = 3;
			auto root = NTree::Init(nums);
			auto res = Solution().amountOfTime(root, start);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod2)
		{
			nums = { 1 }, start = 1;
			auto root = NTree::Init(nums);
			auto res = Solution().amountOfTime(root, start);
			AssertEx(0, res);
		}	

BFS建立临接表

队列记录{父节点编号（BFS序)iPar、当前节点指针cur}，初始{-1,root}。
出队逻辑如下：
如果cur为空，返回。
iCur = neiBo.size();
nieBo.emplace_back()
iPar不是-1,增加iCur和iPar的双向临接。
Add(iCur,cur->left)
Add(iCur,cur->right）

代码

class CBFSLeve {
public :
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	template<class NextFun>
	static vector<int> Leve(int N,NextFun nextFun, vector<int> start) {
		vector<int> leves(N, -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			auto nexts = nextFun(start[i]);
			for (const auto& next : nexts) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]] + 1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	static vector<vector<int>> LeveNodes(const vector<int>& leves) {
		const int iMaxLeve = *max_element(leves.begin(), leves.end());
		vector<vector<int>> ret(iMaxLeve + 1);
		for (int i = 0; i < leves.size(); i++) {
			ret[leves[i]].emplace_back(i);
		}
		return ret;
	};
};

class Solution {
		public:
			int amountOfTime(TreeNode* root, int start) {
				queue<pair<int, TreeNode*>> que ;
				que.emplace(make_pair( -1,root ));
				int iStart = -1;
				vector<vector<int>> neiBo;
				while (que.size()) {
					auto [iPar, cur] = que.front();
					que.pop();
					if (nullptr == cur)continue;
					const int iCur = neiBo.size();
					if (cur->val == start) {
						iStart = iCur;
					}
					neiBo.emplace_back();
					if (-1 != iPar) {
						neiBo[iPar].emplace_back(iCur);
						neiBo[iCur].emplace_back(iPar);
					}
					que.emplace(make_pair(iCur,cur->left));
					que.emplace(make_pair(iCur, cur->right));
				}
				auto leves = CBFSLeve::Leve(neiBo, { iStart });
				return *max_element(leves.begin(), leves.end());
			}
		};