题目描述
思路解析
一句话答案：LeetCode 1315 祖父节点值为偶数的节点和：DFS 往下走时把父节点的值捎带下去，到每个节点只要父值是偶数就把它的孩子加进答案，等价于祖父为偶就计孙子，一趟遍历 O(n)。
要计入的是哪些节点、祖父怎么算
给一棵二叉树，要挑出所有『祖父的值是偶数』的节点，把它们的值加起来。三代关系别搅混：父节点在上一层，祖父再往上一层；节点算不算只看祖父的奇偶，和它自己、和父亲都无关。题面这棵树 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 的孙子照样加。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:DFS 往下走时把父、祖父两个值带在手上,到每个节点抬头看祖父是不是偶数,是就把自己加进答案。下面每一帧都在套这个动作。
总览 · 整棵树：先看清这棵树。一共 11 个节点,我们会用深度优先把它们一个一个走到。约定一下颜色:紫色是当前正在看的节点,蓝色是它的父节点,红色是正被检查奇偶的祖父节点,绿色表示这个节点已经被计入答案。现在当前和是 0。
访问 · 节点 6：走到节点 6。它是根,既没有父节点也没有祖父。没有祖父就谈不上计入,直接跳过,继续往下走。
访问 · 节点 7：走到节点 7。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
访问 · 节点 12：走到节点 12。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
计入 · 节点 12：祖父 6 是偶数,条件满足。把当前节点 12 加进答案,它变成绿色。当前和从 0 涨到 12。
访问 · 节点 9：走到节点 9。它的父节点是 12,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
跳过 · 节点 9：祖父 7 是奇数,条件不满足。当前节点 9 不计入,它标红表示被排除。当前和保持 12 不变。
访问 · 节点 5：走到节点 5。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
计入 · 节点 5：祖父 6 是偶数,条件满足。把当前节点 5 加进答案,它变成绿色。当前和从 12 涨到 17。
访问 · 节点 4：走到节点 4。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
跳过 · 节点 4：祖父 7 是奇数,条件不满足。当前节点 4 不计入,它标红表示被排除。当前和保持 17 不变。
访问 · 节点 11：走到节点 11。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
跳过 · 节点 11：祖父 7 是奇数,条件不满足。当前节点 11 不计入,它标红表示被排除。当前和保持 17 不变。
小结 · 左支处理完：左边以 7 为根的这一支处理完了。目前计入了 12 和 5,当前和 17。注意计入的都是「祖父是偶数 6」那一层的节点;它们下面的孩子祖父变成了奇数 7,所以全被跳过。接着看右边以 8 为根的这一支。
访问 · 节点 8：走到节点 8。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
访问 · 节点 10：走到节点 10。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
计入 · 节点 10：祖父 6 是偶数,条件满足。把当前节点 10 加进答案,它变成绿色。当前和从 17 涨到 27。
访问 · 节点 3：走到节点 3。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
计入 · 节点 3：祖父 6 是偶数,条件满足。把当前节点 3 加进答案,它变成绿色。当前和从 27 涨到 30。
访问 · 节点 15：走到节点 15。它的父节点是 3,祖父节点是 8。判定只看祖父:接下来检查祖父 8 是奇是偶。
计入 · 节点 15：祖父 8 是偶数,条件满足。把当前节点 15 加进答案,它变成绿色。当前和从 30 涨到 45。
答案集合 · 5 个绿节点：遍历结束,绿色的就是被选中的 5 个节点:12、5、10、3、15。它们的共同点是祖父的值都是偶数。把它们加起来:12 加 5 加 10 加 3 加 15,等于 45。
回放 · 为什么是这 5 个：回顾一下:12、5、10、3 的祖父都是根节点 6,6 是偶数,所以入选;15 的祖父是 8,8 也是偶数,入选。剩下的节点要么祖父是奇数 7,要么是根和根的孩子根本没有祖父,所以都没算进来。答案就是 45。
边界先想清:单节点和两层树都没有祖父所以是 0;三层树里最底下那个节点祖父是偶数 6,才开始有值。
面试重点:DFS 自顶向下会丢上层信息所以要带参数、层序记父指针也能做但更繁琐、参考代码的「父偶数加孩子」是看祖父的等价变形。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = rightclass 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)复杂度
- 时间：O(n)，n 是节点总数。每个节点在 DFS 里只被访问一次,访问时做的判断和累加都是常数操作,所以总时间和节点数成正比
- 空间：O(h)，额外空间是递归调用栈,峰值深度等于树高 h。树退化成一条链时 h 等于 n,最坏 O(n);树比较平衡时 h 约为以 2 为底 n 的对数。除递归栈外只用了几个变量
易错点
面试追问把动画讲成自己的话
追问为什么递归时要额外把父节点、祖父节点的值往下传?
追问用广度优先的层序遍历能做吗?
追问参考代码为什么写成「父节点值是偶数就加孩子」,而不是直接看祖父?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除给定值的叶子节点
LeetCode 1325 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题