祖父节点值为偶数的节点和 图解题解

要计入的是哪些节点、祖父怎么算

给一棵二叉树，要挑出所有『祖父的值是偶数』的节点，把它们的值加起来。三代关系别搅混：父节点在上一层，祖父再往上一层；节点算不算只看祖父的奇偶，和它自己、和父亲都无关。题面这棵树 root=[6,7,8,12,5,10,3,9,null,4,11,null,null,null,15] 选出 5 个节点、和 45；单节点 root=[1] 没祖父，输出 0。

给每个节点回头找祖父，慢在哪里

一个节点的祖父在它上面两层。最省心的想法是对每个节点往上跳两格找祖父再看奇偶。可深度优先是自顶向下走的，顺一条路下钻到底再回头，真站到某节点时它上面两层手里并没有。想补就得额外存指回父亲的指针层层上查，信息刚路过却没带在手上。

把父节点的值当参数一路带下去

到了节点再回头找祖父很别扭，不如换个方向：往下走时顺手把祖父信息捎上。给递归多加一个参数 x，存当前节点父亲的值；下钻到孩子时把当前节点的值当成新 x 传下去，每层的 x 就是这层父亲的值。

站在某个节点上，x 就是它父亲的值。x 是偶数时，这个节点两个孩子的祖父正好是这个偶数，父值为偶就把孩子加进答案。这跟『抬头看祖父是不是偶数』数的是同一批节点，只是落脚点从孙子挪到父亲这层——在父亲处提前替孙子做奇偶判断。

递归在每个节点加什么、返回什么

写成递归 dfs(node, x)：空节点返回 0；否则先递归左右孩子，传下去的父值换成当前节点的值，即 dfs(左, node.val) 加 dfs(右, node.val)，收回两棵子树的合格节点和。再看 x：偶数就把当前节点左右孩子的值加到 ans，奇数不加，最后返回 ans。

整棵树的答案就是根这次调用的返回值，由每层子树和逐层汇总。最外层从 dfs(root, 1) 起手，根的父值 1 是奇数，所以根和它两个孩子都不计入，对上『根没有祖父、根的孩子也没有祖父』。

拿题面这棵树逐个节点走一遍

沿题面这棵树走，盯每个节点的父值。根 6 父值取 1、奇数不加；走到 7，父值 6 偶数，把 7 的孩子 12、5 加进答案，和从 0 到 17；走到 8，父值也是 6，把 10、3 加进来，和到 30。

往深走：12 的父值 7、奇数，孩子 9 不加；5 的父值 7，孩子 4、11 不加；10 的父值 8 偶数但没孩子，加 0；3 的父值 8，有孩子 15，加 15，和到 45。9、4、11、15 是叶子，加 0。答案 45，正是选中的 12、5、10、3、15 之和，祖父都是偶数 6 或 8。

根和根的孩子为什么永远算不进来

复杂度上，每个节点只走一遍，做的判断和加法都是常数，时间 O(n)，n 是节点总数；额外开销是递归下钻的调用栈，峰值等于树高 O(h)，枝叶铺得均匀时 h 压在 log n 量级，整棵树斜成一条链时 h 才涨到 n。

几个写错处后果都不轻：把判定看成父亲或自己的奇偶，选出的整批节点都错；硬给根和根的孩子凑祖父，上面不够两层纯属虚构；看到节点自己是奇数就不敢加也不对，自身奇偶从不参与判定，祖父 6 偶数时值 3 的孙子照样加。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, x: int) -> int:
            if root is None:
                return 0
            ans = dfs(root.left, root.val) + dfs(root.right, root.val)
            if x % 2 == 0:
                if root.left:
                    ans += root.left.val
                if root.right:
                    ans += root.right.val
            return ans

        return dfs(root, 1)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * 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) {
        function<int(TreeNode*, int)> dfs = [&](TreeNode* root, int x) {
            if (!root) {
                return 0;
            }
            int ans = dfs(root->left, root->val) + dfs(root->right, root->val);
            if (x % 2 == 0) {
                if (root->left) {
                    ans += root->left->val;
                }
                if (root->right) {
                    ans += root->right->val;
                }
            }
            return ans;
        };
        return dfs(root, 1);
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return dfs(root, 1);
    }

    private int dfs(TreeNode root, int x) {
        if (root == null) {
            return 0;
        }
        int ans = dfs(root.left, root.val) + dfs(root.right, root.val);
        if (x % 2 == 0) {
            if (root.left != null) {
                ans += root.left.val;
            }
            if (root.right != null) {
                ans += root.right.val;
            }
        }
        return ans;
    }
}