Medium

题目描述

给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：该节点的祖父节点的值为偶数。

（一个节点的祖父节点是指该节点的父节点的父节点。）

如果不存在祖父节点值为偶数的节点，那么返回 0 。

示例 1：

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

示例 2：

输入：root = [1]
输出：0

提示：

  • 树中节点的数目在 [1, 10^4] 范围内。
  • 1 <= Node.val <= 100

提示：

  • 遍历树时保持父节点和祖父节点的信息。
  • 如果当前节点的祖父节点值为偶数，将该节点的值加入答案。

解题思路

这道题要求找到祖父节点值为偶数的所有节点，并返回它们的值的和。

解题思路：

核心思想是在二叉树遍历过程中维护父节点和祖父节点的信息。当访问到某个节点时，如果其祖父节点的值为偶数，就将当前节点的值累加到结果中。

主要解法：

  1. DFS递归解法：使用深度优先搜索，在递归函数中传递祖父节点和父节点的值。这是最直观的解法。

  2. BFS解法：使用广度优先搜索配合队列，将节点及其父节点和祖父节点信息一同存储。

  3. 优化的DFS解法：可以直接传递祖父节点和父节点的引用，避免传值的开销。

推荐使用DFS递归解法，因为代码简洁易懂，且时间复杂度最优。

在实现时，我们从根节点开始递归遍历，对于每个节点，检查其祖父节点是否存在且值为偶数。如果条件满足，就将当前节点的值加入结果。然后递归处理左右子树，更新父节点和祖父节点的信息。

代码实现

class Solution {
public:
    int sumEvenGrandparent(TreeNode* root) {
        return dfs(root, nullptr, nullptr);
    }
    
private:
    int dfs(TreeNode* node, TreeNode* parent, TreeNode* grandparent) {
        if (!node) return 0;
        
        int sum = 0;
        if (grandparent && grandparent->val % 2 == 0) {
            sum += node->val;
        }
        
        sum += dfs(node->left, node, parent);
        sum += dfs(node->right, node, parent);
        
        return sum;
    }
};

class Solution:
    def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
        def dfs(node, parent, grandparent):
            if not node:
                return 0
            
            result = 0
            if grandparent and grandparent.val % 2 == 0:
                result += node.val
            
            result += dfs(node.left, node, parent)
            result += dfs(node.right, node, parent)
            
            return result
        
        return dfs(root, None, None)

public class Solution {
    public int SumEvenGrandparent(TreeNode root) {
        return Dfs(root, null, null);
    }
    
    private int Dfs(TreeNode node, TreeNode parent, TreeNode grandparent) {
        if (node == null) return 0;
        
        int sum = 0;
        if (grandparent != null && grandparent.val % 2 == 0) {
            sum += node.val;
        }
        
        sum += Dfs(node.left, node, parent);
        sum += Dfs(node.right, node, parent);
        
        return sum;
    }
}

var sumEvenGrandparent = function(root) {
    let sum = 0;
    
    function dfs(node, parent, grandparent) {
        if (!node) return;
        
        if (grandparent && grandparent.val % 2 === 0) {
            sum += node.val;
        }
        
        dfs(node.left, node, parent);
        dfs(node.right, node, parent);
    }
    
    dfs(root, null, null);
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历二叉树的每个节点一次，其中 n 是节点总数
空间复杂度O(h)递归调用栈的深度，其中 h 是二叉树的高度，最坏情况下为 O(n)