1315. Sum of Nodes with Even-Valued Grandparent**

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

题目描述

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

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.

Constraints:

• The number of nodes in the tree is between 1 and 10^4.
• The value of nodes is between 1 and 100.

C++ 实现 0

(20210311) 时隔一年, 原来一开始没找到正确方向的题, 现在终于能快速发现思路了, 前序遍历, 对每个节点, 判断它是否能被 2 整除, 能的话, 再累加 grandchild 节点之和.

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

另外在 LeetCode 的提交中看到一种写法, 比较简洁:

dfs 中同时传入 root 以及它的孩子, 这样访问 grandchild 更方便.

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

C++ 实现 1

先给出 LeetCode Submission 中的一个解法, 很直接.

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {int totalSum = 0;helper(root , totalSum);return totalSum;}void helper(TreeNode *root , int &totalSum){if(root){if(root->val % 2 ==0){if(root->left){if(root->left->left){totalSum += root->left->left->val;}if(root->left->right){totalSum += root->left->right->val;}}if(root->right){if(root->right->left){totalSum += root->right->left->val;}if(root->right->right){totalSum += root->right->right->val;}}}helper(root->left , totalSum);helper(root->right , totalSum);}}
};

C++ 实现 2

我的提交, 思路和 C++ 实现 1 是一样的, 但是在计算 grandson 的总和是用的队列的方法… 比较慢, beats 8% 🥺

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:int sum = 0;int sumGrandSon(TreeNode *root) {if (!root) return 0;int sum = 0;queue<TreeNode*> q;q.push(root);int level = 0;while (!q.empty()) {auto size = q.size();level += 1;while (size --) {auto r = q.front();q.pop();if (level == 3) sum += r->val;if (r->left) q.push(r->left);if (r->right) q.push(r->right);}}return sum;}void preorder(TreeNode *root) {if (!root) return;if (root->val % 2 == 0) sum += sumGrandSon(root);preorder(root->left);preorder(root->right);}
public:int sumEvenGrandparent(TreeNode* root) {preorder(root);return sum;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！