最开始看到这题想到用BFS实现,写完后才发现不行,如果当前行存在偶数,我下面的代码,会把下下行的结点加进去。
/**
* 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) {
//BFS
if(root == NULL) return 0;
queue<TreeNode *> queue;
int sum = 0,depth = 0;
queue.push(root);
unordered_set<int> hash;
while(!queue.empty())
{
int size = queue.size();
for(int i = 0;i < size;i++)
{
TreeNode* grand = queue.front();
queue.pop();
if(hash.count(depth))
{
sum += grand->val;
}
if(grand->val %2 == 0) hash.insert(depth + 2);
if(grand->left) queue.push(grand->left);
if(grand->right) queue.push(grand->right);
}
depth += 1;
}
return sum;
}
};
修改后可AC的代码如下:
/**
* 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) {
//BFS
if(root == NULL) return 0;
queue<TreeNode *> queue;
int sum = 0;
queue.push(root);
while(!queue.empty())
{
int size = queue.size();
for(int i = 0;i < size;i++)
{
TreeNode* grand = queue.front();
queue.pop();
if(grand->val %2 == 0)
{
if(grand->left)
{
sum += get_node_value(grand->left->left);
sum += get_node_value(grand->left->right);
}
if(grand->right)
{
sum += get_node_value(grand->right->left);
sum += get_node_value(grand->right->right);
}
}
if(grand->left) queue.push(grand->left);
if(grand->right) queue.push(grand->right);
}
}
return sum;
}
private:
int get_node_value(TreeNode *root)
{
if(root == NULL) return 0;
return root->val;
}
};