2385. 感染二叉树需要的总时间
题目链接:2385. 感染二叉树需要的总时间
代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//记录父节点 + DFS
//参考链接:https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/2753470/cong-liang-ci-bian-li-dao-yi-ci-bian-li-tmt0x
class Solution {
public:
void dfs(TreeNode* node,TreeNode* from)
{
if(node==nullptr) return;
fa[node->val]=from;//记录每个结点的父节点
if(node->val==start)//找到start节点
{
start_node=node;
}
dfs(node->left,node);
dfs(node->right,node);
}
int maxDepth(TreeNode* node,TreeNode* from)
{
if(node==nullptr) return -1;
int res=-1;
if(node->left!=from)
{
res=max(res,maxDepth(node->left,node));
}
if(node->right!=from)
{
res=max(res,maxDepth(node->right,node));
}
if(fa[node->val]!=from)
{
res=max(res,maxDepth(fa[node->val],node));
}
return res+1;
}
int amountOfTime(TreeNode* root, int start)
{
this->start=start;
dfs(root,nullptr);
return maxDepth(start_node,start_node);
}
private:
int start;
TreeNode* start_node;
TreeNode* fa[100001];
};