一、题目
1、题目描述
给你一棵二叉树的根节点
root
,二叉树中节点的值 互不相同 。另给你一个整数start
。在第0
分钟,感染 将会从值为start
的节点开始爆发。每分钟,如果节点满足以下全部条件,就会被感染:
- 节点此前还没有感染。
- 节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
2、接口描述
python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
cpp
/**
* 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) {}
* };
*/
class Solution {
public:
int amountOfTime(TreeNode* root, int start) {
}
};
3、原题链接
二、解题报告
1、思路分析
答案很明显就是求start向上最大距离和向下最大距离中大的那个
这个还是很好求的,我们可以两次dfs,开两个数组记录下值,就是一个换根dp,换根到start的时候就返回答案即可
不过更优雅的做法是,我们发现答案来自两部分:start向下最大距离,根节点到start的距离加上从另一颗子树向下的最大距离
那么实际上我们进行一次dfs即可
如果找到start或者子树中找到start,我们向上返回深度的时候就返回到达start的距离
如果没找到,就返回到最远子节点的距离的相反数
2、复杂度
时间复杂度: O(n) 空间复杂度:O(n)
3、代码详解
python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
ret = 0
def dfs(rt: Optional[TreeNode]) -> int:
if rt is None:
return 0
L = dfs(rt.left)
R = dfs(rt.right)
nonlocal ret
if rt.val == start:
ret = max(ret, -min(L, R))
return 1
if L > 0 or R > 0:
ret = max(ret, abs(L) + abs(R))
return max(L, R) + 1
return min(L, R) - 1
dfs(root)
return ret
cpp
/**
* 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) {}
* };
*/
class Solution {
public:
int ret, start;
int dfs(TreeNode* root){
if(!root) return 0;
int L = dfs(root->left), R = dfs(root->right);
if(root->val == start){
ret = -min(L, R);
return 1;
}
if(L > 0 || R > 0){
ret = max(ret, abs(L) + abs(R));
return max(L, R) + 1;
}
return min(L, R) - 1;
}
int amountOfTime(TreeNode* root, int start) {
ret = 0, this->start = start;
dfs(root);
return ret;
}
};