LeetCode 题解工作台
祖父节点值为偶数的节点和
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和： 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。） 如果不存在祖父节点值为偶数的节点，那么返回 0 。 示例： 输入： root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 $dfs(root, x)$，表示以 为根节点，并且 的父节点的值为 的子树中，满足条件的节点的值之和。那么答案就是 $dfs(root, 1)$。 函数 $dfs(root, x)$ 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
- 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。
示例：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出：18 解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
提示：
- 树中节点的数目在
1到10^4之间。 - 每个节点的值在
1到100之间。
解题思路
方法一：DFS
我们设计一个函数 ，表示以 为根节点，并且 的父节点的值为 的子树中，满足条件的节点的值之和。那么答案就是 。
函数 的执行过程如下：
- 如果 为空，返回 。
- 否则，我们递归计算 的左子树和右子树的答案，即 和 ，累加到答案中。如果 为偶数，此时我们判断 的左孩子和右孩子是否存在，如果存在，我们将它们的值累加到答案中。
- 最后返回答案。
时间复杂度 ，空间复杂度 。其中 为节点个数。
# 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 sumEvenGrandparent(self, root: TreeNode) -> int:
def dfs(root: TreeNode, x: int) -> int:
if root is None:
return 0
ans = dfs(root.left, root.val) + dfs(root.right, root.val)
if x % 2 == 0:
if root.left:
ans += root.left.val
if root.right:
ans += root.right.val
return ans
return dfs(root, 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Ability to keep track of state while traversing the tree.
- question_mark
Efficient use of tree traversal techniques, either DFS or BFS.
- question_mark
Clear understanding of parent-child relationships and their role in tree traversal.
常见陷阱
外企场景- error
Failing to properly maintain the state of parent and grandparent nodes during traversal.
- error
Not considering edge cases such as a tree with only one node or no even-valued grandparents.
- error
Using a non-optimal tree traversal technique that leads to unnecessary complexity or memory usage.
进阶变体
外企场景- arrow_right_alt
Modify the problem to sum nodes with odd-valued grandparents.
- arrow_right_alt
Add a constraint that the tree is balanced or sorted in some way.
- arrow_right_alt
Consider different tree types, such as AVL or Red-Black trees, and adapt the traversal accordingly.