[LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Input: root = [1]
Output: 0

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 1 <= Node.val <= 100

这道题给了一棵二叉树，让返回具有偶数值爷结点的所有结点的值之和，何为爷结点，就是父结点的父结点。需要找出所有爷结点值是偶数的结点，并返回它们的结点值之和，注意不是返回爷结点值之和。根据以往的经验，二叉树的题目大多情况下都是用递归的解法，这道题也不例外，遍历顺序就用先序遍历就可以了。在递归函数中，首先判空，若为空，直接返回。否则看当前结点值是否为偶数，是的话就去找其孙结点，一共有四个孙结点，若左子结点存在的话，分别判断其两个孙结点是否存在，存在的话就将其结点值加到 res 中，同理，若右子结点存在的话，分别判断其两个孙结点是否存在，存在的话就将其结点值加到 res 中，然后在分别对左右子结点调用递归函数即可，参见代码如下：

解法一：

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

上面解法的判断有些复杂，这是因为是在找当前结点的四个孙结点，若是直接处理每个孙结点的话，就会相对简单一些。但此时必须要知道孙结点的爷结点，同时也要知道父结点，因为一旦去递归子结点时，之前的父结点就是新的爷结点，所以在递归函数中要把父结点和爷结点当参数传进去。在递归函数中还是先判空，然后判断若爷结点存在，并且值为偶数，则将当前结点值加到 res 中，然后分别对左右子结点调用递归函数，当前结点和父结点就变成了新的父结点和爷结点当参数传入即可，参见代码如下：

解法二：

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1315

参考资料：

https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/

https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/discuss/477095/Easy-DFS-solution

https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/discuss/477048/JavaC%2B%2BPython-1-Line-Recursive-Solution

LeetCode All in One 题目讲解汇总(持续更新中...)