解法一：广度优先遍历

广度优先遍历，对于值为偶数的结点，对其孙子结点求和。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int sumEvenGrandparent(TreeNode root) {
  12.         Queue<TreeNode> queue = new LinkedList<>();
  13.         if (root != null) {
  14.             queue.offer(root);
  15.         }
  16.         int sum = 0;
  17.         while (!queue.isEmpty()) {
  18.             TreeNode tmp = queue.poll();
  19.             // 对四个可能的孙子结点求和
  20.             if (tmp.val % 2 == 0) {
  21.                 if (tmp.left != null) {
  22.                     if (tmp.left.left != null) {
  23.                         sum += tmp.left.left.val;
  24.                     }
  25.                     if (tmp.left.right != null) {
  26.                         sum += tmp.left.right.val;
  27.                     }
  28.                 }
  29.                 if (tmp.right != null) {
  30.                     if (tmp.right.left != null) {
  31.                         sum += tmp.right.left.val;
  32.                     }
  33.                     if (tmp.right.right != null) {
  34.                         sum += tmp.right.right.val;
  35.                     }
  36.                 }
  37.             }
  38.             if (tmp.left != null) {
  39.                 queue.offer(tmp.left);
  40.             }
  41.             if (tmp.right != null) {
  42.                 queue.offer(tmp.right);
  43.             }
  44.         }
  45.         return sum;
  46.     }
  47. }

解法二：深度优先遍历

基本同上，但采用深度优先遍历。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int sumEvenGrandparent(TreeNode root) {
  12.         return dfs(root);
  13.     }
  15.     private int dfs(TreeNode root) {
  16.         if (root == null) {
  17.             return 0;
  18.         }
  19.         int sum = 0;
  20.         // 对四个可能的孙子结点求和
  21.         if (root.val % 2 == 0) {
  22.             if (root.left != null) {
  23.                 if (root.left.left != null) {
  24.                     sum += root.left.left.val;
  25.                 }
  26.                 if (root.left.right != null) {
  27.                     sum += root.left.right.val;
  28.                 }
  29.             }
  30.             if (root.right != null) {
  31.                 if (root.right.left != null) {
  32.                     sum += root.right.left.val;
  33.                 }
  34.                 if (root.right.right != null) {
  35.                     sum += root.right.right.val;
  36.                 }
  37.             }
  38.         }
  39.         if (root.left != null) {
  40.             sum += dfs(root.left);
  41.         }
  42.         if (root.right != null) {
  43.             sum += dfs(root.right);
  44.         }
  45.         return sum;
  46.     }
  47. }