题目描述
思路解析动画文字版
记牢一句: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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题