感染二叉树需要的总时间

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

给你一棵二叉树的根节点 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 的节点

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * 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) { } };

rust 解法, 执行用时: 39 ms, 内存消耗: 17.7 MB, 提交时间: 2024-04-24 09:17:40

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn amount_of_time(root: Option<Rc<RefCell<TreeNode>>>, start: i32) -> i32 {
        fn dfs(node: Option<&Rc<RefCell<TreeNode>>>, start: i32, ans: &mut i32) -> i32 {
            if let Some(x) = node {
                let x = x.borrow();
                let l_len = dfs(x.left.as_ref(), start, ans);
                let r_len = dfs(x.right.as_ref(), start, ans);
                if x.val == start {
                    // 计算子树 start 的最大深度
                    *ans = -l_len.min(r_len); // 负负得正
                    return 1; // 用正数表示找到了 start
                }
                if l_len > 0 || r_len > 0 {
                    // 只有在左子树或右子树包含 start 时，才能更新答案
                    *ans = (*ans).max(l_len.abs() + r_len.abs()); // 两条链拼成直径
                    return l_len.max(r_len) + 1; // max 会自动取到正数
                }
                return l_len.min(r_len) - 1 // 用负数表示没有找到 start
            }
            0
        }
        let mut ans = 0;
        dfs(root.as_ref(), start, &mut ans);
        ans
    }
}

javascript 解法, 执行用时: 197 ms, 内存消耗: 97.8 MB, 提交时间: 2024-04-24 09:17:21

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    let ans = 0;
    function dfs(node) {
        if (node === null) {
            return 0;
        }
        const lLen = dfs(node.left);
        const rLen = dfs(node.right);
        if (node.val === start) {
            // 计算子树 start 的最大深度
            ans = -Math.min(lLen, rLen); // 负负得正
            return 1; // 用正数表示找到了 start
        }
        if (lLen > 0 || rLen > 0) {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = Math.max(ans, Math.abs(lLen) + Math.abs(rLen)); // 两条链拼成直径
            return Math.max(lLen, rLen) + 1; // max 会自动取到正数
        }
        return Math.min(lLen, rLen) - 1; // 用负数表示没有找到 start
    }
    dfs(root);
    return ans;
};

cpp 解法, 执行用时: 108 ms, 内存消耗: 90.5 MB, 提交时间: 2024-04-24 09:16:54

/**
 * 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 {
    int ans = 0, start;

    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int l_len = dfs(node->left);
        int r_len = dfs(node->right);
        if (node->val == start) {
            // 计算子树 start 的最大深度
            ans = -min(l_len, r_len); // 负负得正
            return 1; // 用正数表示找到了 start
        }
        if (l_len > 0 || r_len > 0) {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = max(ans, abs(l_len) + abs(r_len)); // 两条链拼成直径
            return max(l_len, r_len) + 1; // max 会自动取到正数
        }
        return min(l_len, r_len) - 1; // 用负数表示没有找到 start
    }

public:
    int amountOfTime(TreeNode* root, int start) {
        this->start = start;
        dfs(root);
        return ans;
    }
};

java 解法, 执行用时: 10 ms, 内存消耗: 76.3 MB, 提交时间: 2024-04-24 09:16:41

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;

    public int amountOfTime(TreeNode root, int start) {
        dfs(root, start);
        return ans;
    }

    private int dfs(TreeNode node, int start) {
        if (node == null) {
            return 0;
        }
        int lLen = dfs(node.left, start);
        int rLen = dfs(node.right, start);
        if (node.val == start) {
            // 计算子树 start 的最大深度
            ans = -Math.min(lLen, rLen); // 负负得正
            return 1; // 用正数表示找到了 start
        }
        if (lLen > 0 || rLen > 0) {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = Math.max(ans, Math.abs(lLen) + Math.abs(rLen)); // 两条链拼成直径
            return Math.max(lLen, rLen) + 1; // max 会自动取到正数
        }
        return Math.min(lLen, rLen) - 1; // 用负数表示没有找到 start
    }
}

golang 解法, 执行用时: 160 ms, 内存消耗: 33.1 MB, 提交时间: 2024-04-24 09:16:28

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func amountOfTime(root *TreeNode, start int) (ans int) {
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        lLen := dfs(node.Left)
        rLen := dfs(node.Right)
        if node.Val == start {
            // 计算子树 start 的最大深度
            ans = -min(lLen, rLen) // 负负得正
            return 1 // 用正数表示找到了 start
        }
        if lLen > 0 || rLen > 0 {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = max(ans, abs(lLen)+abs(rLen)) // 两条链拼成直径
            return max(lLen, rLen) + 1 // max 会自动取到正数
        }
        return min(lLen, rLen) - 1 // 用负数表示没有找到 start
    }
    dfs(root)
    return
}

func abs(x int) int { if x < 0 { return -x }; return x }

python3 解法, 执行用时: 261 ms, 内存消耗: 52.5 MB, 提交时间: 2024-04-24 09:16:09

# 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:
        ans = 0
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            l_len = dfs(node.left)
            r_len = dfs(node.right)
            nonlocal ans
            if node.val == start:
                # 计算子树 start 的最大深度
                ans = -min(l_len, r_len)  # 负负得正
                return 1  # 用正数表示找到了 start
            if l_len > 0 or r_len > 0:
                # 只有在左子树或右子树包含 start 时，才能更新答案
                ans = max(ans, abs(l_len) + abs(r_len))  # 两条链拼成直径
                return max(l_len, r_len) + 1  # max 会自动取到正数
            return min(l_len, r_len) - 1  # 用负数表示没有找到 start
        dfs(root)
        return ans

golang 解法, 执行用时: 292 ms, 内存消耗: 35.7 MB, 提交时间: 2023-08-28 10:31:44

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func amountOfTime(root *TreeNode, start int) int {
	var st *TreeNode
	parents := map[*TreeNode]*TreeNode{}
	var dfs func(*TreeNode, *TreeNode)
	dfs = func(node, pa *TreeNode) {
		if node == nil {
			return
		}
		if node.Val == start {
			st = node
		}
		parents[node] = pa
		dfs(node.Left, node)
		dfs(node.Right, node)
	}
	dfs(root, nil)

	ans := -1
	vis := map[*TreeNode]bool{nil: true, st: true}
	for q := []*TreeNode{st}; len(q) > 0; ans++ {
		tmp := q
		q = nil
		for _, node := range tmp {
			if node != nil {
				if !vis[node.Left] {
					vis[node.Left] = true
					q = append(q, node.Left)
				}
				if !vis[node.Right] {
					vis[node.Right] = true
					q = append(q, node.Right)
				}
				if p := parents[node]; !vis[p] {
					vis[p] = true
					q = append(q, p)
				}
			}
		}
	}
	return ans
}

python3 解法, 执行用时: 532 ms, 内存消耗: 144.8 MB, 提交时间: 2023-08-28 10:31:30

# 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:
        parents = {}
        def dfs(node: Optional[TreeNode], pa: Optional[TreeNode]) -> None:
            if node is None: return
            if node.val == start: self.start = node
            parents[node] = pa
            dfs(node.left, node)
            dfs(node.right, node)
        dfs(root, None)

        ans = -1
        vis = {None, self.start}
        q = [self.start]
        while q:
            ans += 1
            tmp = q
            q = []
            for node in tmp:
                for x in node.left, node.right, parents[node]:
                    if x not in vis:
                        vis.add(x)
                        q.append(x)
        return ans

上一题

下一题

详情