链接：https://leetcode-cn.com/problems/sum-of-nodes-with-even-valued-grandparent/
难度：medium
解题思路：广搜，构造一个新的类，用来记录当前节点，父亲，祖父的关系，广搜的队列操作中就对关系进行搜索，每次遍历道的节点，如果符合要求就加到result上，广搜完成后，result 就是答案
class Solution {
static class Link {
TreeNode self;
TreeNode parent;
TreeNode grandParent;
public Link(TreeNode self, TreeNode parent, TreeNode grandParent) {
this.self = self;
this.parent = parent;
this.grandParent = grandParent;
}
}
public int sumEvenGrandparent(TreeNode root) {
Link link = new Link(root, null, null);
Queue<Link> queue = new LinkedList<Link>();
queue.offer(link);
int result = 0;
Link h;
while((h = queue.poll()) != null) {
if(h.parent != null && h.grandParent != null && h.grandParent.val % 2 == 0) {
result += h.self.val;
}
if(h.self.left != null) {
Link l = new Link(h.self.left, h.self, h.parent);
queue.offer(l);
}
if(h.self.right != null) {
Link r = new Link(h.self.right, h.self, h.parent);
queue.offer(r);
}
}
return result;
}
}
执行用时：8 ms, 在所有 Java 提交中击败了10.67%的用户
内存消耗：39.4 MB, 在所有 Java 提交中击败了95.65%的用户
更简便的办法，不需要辅助类的解法，就是遍历根结点时，直接看他的曾孙是否需要加到result上。
class Solution {
public int sumEvenGrandparent(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int result = 0;
TreeNode h;
while((h = queue.poll()) != null) {
if(h.left != null) {
queue.offer(h.left);
}
if(h.right != null) {
queue.offer(h.right);
}
if(h.val % 2 == 0) {
if(h.left != null) {
if(h.left.left != null) {
result += h.left.left.val;
}
if(h.left.right != null) {
result += h.left.right.val;
}
}
if(h.right != null) {
if(h.right.left != null) {
result += h.right.left.val;
}
if(h.right.right != null) {
result += h.right.right.val;
}
}
}
}
return result;
}
}
执行用时：6 ms, 在所有 Java 提交中击败了15.42%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了89.33%的用户
