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

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

🎯 问题描述（来源于LeetCode）

描述：
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0。

• 示例：
  • 示例 1：

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

💻 解题思路

思路1：DFS 深度优先搜索（状态传递）

代码实现

from typing import Optional

class Solution:
    def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, f=None, g=None):
            if node is None:
                return 
            
            nonlocal ans
            # 如果祖父节点存在且为偶数，累加当前节点的值
            if g is not None and g & 1 == 0:
                ans += node.val
            
            # 递归遍历左右子树，更新父节点和祖父节点的值
            dfs(node.left, node.val, f)
            dfs(node.right, node.val, f)
        
        dfs(root)
        return ans

📊 性能分析

• 时间复杂度：$O(n)$。其中 $n$ 为二叉树的节点数，每个节点只会被访问一次。
• 空间复杂度：$O(h)$。其中 $h$ 为二叉树的高度，主要为递归调用栈的空间开销。

💡 思考

这道题的核心在于**“跨层级的状态传递”**。

1. 普通的 DFS 只需要关注当前节点，而这道题需要知道当前节点的“祖父节点”的状态。
2. 我们通过在递归函数中增加 f (父节点值) 和 g (祖父节点值) 两个参数，实现了状态的向下传递。
3. 每次递归时，当前节点的值变成下一层的父节点值 (f)，当前的父节点值变成下一层的祖父节点值 (g)。
4. 使用位运算 g & 1 == 0 来判断偶数，是比取模运算更高效的底层技巧。