【算法】1315. 祖父节点值为偶数的节点和（多语言实现）

• 1315. 祖父节点值为偶数的节点和：
• 样例 1：
• 提示：
• 分析
• 题解
• • rust
  • go
  • typescript
  • c
  • c++
  • java
  • python
• 原题传送门：https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/

给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：

• 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）

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

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

• 树中节点的数目在 1 到 1 0 4 10^4 104 之间。
• 每个节点的值在 1 到 100 之间。

• 面对这道算法题目，二当家的陷入了沉思。
• 遍历结构，一般就是使用循环或是递归，这里显然递归更加直观易懂，所以选择使用套娃递归大法。
• 二叉树的关联是单向的，无法从一个节点关联到它的祖父节点，所以我们需要把祖父节点或者说祖父节点的信息传递到递归中。
• 父亲节点将会是当前节点子节点的祖父节点，而且也无法从一个节点关联到它的父亲节点，所以父亲节点的信息也要一并传递到递归中。

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option>>,
//   pub right: Option>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_even_grandparent(root: Option>>) -> i32 {
        fn dfs(mut node: Option>>, parentIsEven: bool, grandparentIsEven: bool) -> i32 {
            match node {
                Some(node) => {
                    let mut ans = 0;
                    
                    let mut node = node.borrow_mut();
                    if grandparentIsEven {
                        ans += node.val;
                    }

                    ans += dfs(node.left.take(), node.val & 1 == 0, parentIsEven);
                    ans += dfs(node.right.take(), node.val & 1 == 0, parentIsEven);
                    
                    ans
                }
                _ => { 0 }
            }
        }

        dfs(root, false, false)
    }
}

func sumEvenGrandparent(root *TreeNode) int {
    var dfs func(*TreeNode, bool, bool) int
	dfs = func(node *TreeNode, parentIsEven bool, grandparentIsEven bool) int {
		if node == nil {
			return 0
		}
		
		ans := 0

		if grandparentIsEven {
			ans += node.Val
		}

		ans += dfs(node.Left, (node.Val & 1) == 0, parentIsEven)
		ans += dfs(node.Right, (node.Val & 1) == 0, parentIsEven)

		return ans
	}

	return dfs(root, false, false)
}

function sumEvenGrandparent(root: TreeNode | null): number {
    const dfs = (node: TreeNode, parentIsEven: Boolean, grandparentIsEven: Boolean): number => {
        if (node == null) {
            return 0;
        }

        let ans = 0;

        if (grandparentIsEven) {
            ans += node.val;
        }

        ans += dfs(node.left, (node.val & 1) == 0, parentIsEven);
        ans += dfs(node.right, (node.val & 1) == 0, parentIsEven);

        return ans;
    };

    return dfs(root, false, false);
};

int dfs(struct TreeNode* node, bool parentIsEven, bool grandparentIsEven) {
    if (node == NULL) {
        return 0;
    }
    
    int ans = 0;

    if (grandparentIsEven) {
        ans += node->val;
    }

    ans += dfs(node->left, (node->val & 1) == 0, parentIsEven);
    ans += dfs(node->right, (node->val & 1) == 0, parentIsEven);

    return ans;
}

int sumEvenGrandparent(struct TreeNode* root){
    return dfs(root, false, false);
}

class Solution {
private:
    int dfs(TreeNode* node, bool parentIsEven, bool grandparentIsEven) {
        if (node == nullptr) {
            return 0;
        }
        
        int ans = 0;

        if (grandparentIsEven) {
            ans += node->val;
        }

        ans += dfs(node->left, (node->val & 1) == 0, parentIsEven);
        ans += dfs(node->right, (node->val & 1) == 0, parentIsEven);

        return ans;
    }
public:
    int sumEvenGrandparent(TreeNode* root) {
        return dfs(root, false, false);
    }
};

class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return dfs(root, false, false);
	}

	private int dfs(TreeNode node, boolean parentIsEven, boolean grandparentIsEvent) {
		if (node == null) {
			return 0;
		}

		int ans = 0;
		
		if (grandparentIsEvent) {
			ans += node.val;
		}

		ans += dfs(node.left, (node.val & 1) == 0, parentIsEven);
		ans += dfs(node.right, (node.val & 1) == 0, parentIsEven);

		return ans;
	}
}

# 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(node: TreeNode, parent_is_even: bool, grandparent_is_even: bool) -> int:
            if node is None:
                return 0
            ans = 0
            if grandparent_is_even:
                ans += node.val
            ans += dfs(node.left, (node.val & 1) == 0, parent_is_even)
            ans += dfs(node.right, (node.val & 1) == 0, parent_is_even)
            return ans
        return dfs(root, False, False)
        

非常感谢你阅读本文~
欢迎【点赞】【⭐收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~