网站开发内容怎么写,南京制作网站,浙江省城乡建设厅网站,大连网站关键字优化给你一棵二叉树#xff0c;请你返回满足以下条件的所有节点的值之和#xff1a;
该节点的祖父节点的值为偶数。#xff08;一个节点的祖父节点是指该节点的父节点的父节点。#xff09; 如果不存在祖父节点值为偶数的节点#xff0c;那么返回 0 。
示例#xff1a; 输入…给你一棵二叉树请你返回满足以下条件的所有节点的值之和
该节点的祖父节点的值为偶数。一个节点的祖父节点是指该节点的父节点的父节点。 如果不存在祖父节点值为偶数的节点那么返回 0 。
示例 输入root [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出18 解释图中红色节点的祖父节点的值为偶数蓝色节点为这些红色节点的祖父节点。
提示
树中节点的数目在 1 到 10^4 之间。 每个节点的值在 1 到 100 之间。
法一直接递归模拟即可
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {int ans 0;findAns(root, false, false, ans);return ans;}private:void findAns(TreeNode *node, bool isEvenFather, bool isEvenGrandFather, int ans){if (node nullptr){return;}if (isEvenGrandFather){ans node-val;}findAns(node-left, !(node-val 1), isEvenFather, ans);findAns(node-right, !(node-val 1), isEvenFather, ans);}
};如果树中有n个节点此算法时间复杂度为O(n)空间复杂度为O(logn)。
法二广度优先搜索每遍历到一个偶数节点将其孙子节点的值加上
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {queueTreeNode * q;q.push(root);int ans 0;while (!q.empty()){TreeNode *node q.front();q.pop();if (!(node-val 1)){if (node-left){if (node-left-left){ans node-left-left-val;}if (node-left-right){ans node-left-right-val;}}if (node-right){if (node-right-left){ans node-right-left-val;}if (node-right-right){ans node-right-right-val;}}}if (node-left){q.push(node-left);}if (node-right){q.push(node-right);}}return ans;}
};如果树中有n个节点此算法时间复杂度为O(n)空间复杂度为O(logn)。
