1315. Sum of nodes with even grandfather node value (medium)

1315. The grandfather node value is an even number of nodes and

Here is a binary tree for you , Please return the sum of the values of all nodes that meet the following conditions ：

The value of the grandfather node of this node is even .（ The grandfather node of a node refers to the parent node of the parent node of the node .）
If there is no node with even value of grandfather node , Then the return 0 .

Example ：

 Input ：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
 Output ：18
 explain ： The value of the grandfather node of the red node in the figure is even , Blue nodes are the grandfather nodes of these red nodes .

Ideas

Save the information of three nodes , They are Grandfather nodes , Parent node and current node

• If the value of the grandfather node satisfies the even condition , be sum Add the value of the current node
• The next recursion , The parent node acts as the parent node , The current node acts as the parent node , Achieve progressive progress layer by layer

Source code

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

Official explanation

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