LEETCODE 1315. Sum of Nodes with Even-Valued Grandparent 解题思路分析

题目大意:

祖父节点值为偶数的节点和

给你一棵二叉树,请你返回满足以下条件的所有节点的值之和:

该节点的祖父节点的值为偶数。(一个节点的祖父节点是指该节点的父节点的父节点。)
如果不存在祖父节点值为偶数的节点,那么返回 0 。

示例:

输入:root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出:18
解释:图中红色节点的祖父节点的值为偶数,蓝色节点为这些红色节点的祖父节点。

提示:

  • 树中节点的数目在 1 到 10^4 之间。
  • 每个节点的值在 1 到 100 之间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1315

解题思路分析:

对于二叉树题目,使用dfs深度优先搜索,或者说是递归方式来解题是比较方便可行的。递归时,参数传入当前节点的父节点以及祖父节点的值,对于根节点,父节点和祖父节点值为1(因为1是奇数,因此不影响接下来的计算)。对于任意节点,如果其祖父节点是偶数,将当前节点的值累加到返回结果。然后继续向下递归其左右子节点,向下递归时,对于其子节点的父节点为当前节点,祖父节点为当前节点的父节点。

实现代码:

int res = 0; // 返回结果
public int sumEvenGrandparent(TreeNode root) {
    // 递归求解
    help(root, 1, 1);
    return res;
}
// root是当前节点
// p为父节点
// g为祖父节点
void help(TreeNode root, int p, int g){
    // 如果祖父节点是偶数,累加当前节点到返回结果
    if(g%2==0) res+=root.val;
    // 如果右子节点不为空,递归。
    // 右子节点的父节点是当前节点,祖父节点是当前父节点
    if(root.right!=null) help(root.right, root.val, p);
    // 如果左子节点不为空,递归。
    // 左子节点的父节点是当前节点,祖父节点是当前父节点
    if(root.left!=null) help(root.left, root.val, p);
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Sum of Nodes with Even-Valued Grandparent.

Memory Usage: 40.6 MB, less than 100.00% of Java online submissions for Sum of Nodes with Even-Valued Grandparent.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1315-sum-of-nodes-with-even-valued-grandparent-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。