LeetCode 1315中等树 · BST

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

这道题到底在问什么

注意三个亲戚关系别搞混:父节点是上面一层,祖父节点是再往上一层。判定一个节点要不要计入,只看它祖父的值是奇是偶,跟这个节点自己、跟它父亲的奇偶都没有关系。一棵树里,根节点没有父亲也没有祖父,根的孩子有父亲但还是没有祖父,所以根和根的孩子永远不会被计入。

输入: root = [6,7,8,12,5,10,3,9,null,4,11,null,null,null,15]
输出: 45
输入: root = [1]
输出: 0

先想最直接的笨办法

先看清这棵树。一共 11 个节点,我们会用深度优先把它们一个一个走到。约定一下颜色:紫色是当前正在看的节点,蓝色是它的父节点,红色是正被检查奇偶的祖父节点,绿色表示这个节点已经被计入答案。现在当前和是 0。（动画第 4 步）

最优解：一步一步想明白

3记牢一句:DFS 往下走时把父、祖父两个值带在手上,到每个节点抬头看祖父是不是偶数,是就把自己加进答案。下面每一帧都在套这个动作。
4当前和 = 0 · 待遍历先看清这棵树。一共 11 个节点,我们会用深度优先把它们一个一个走到。约定一下颜色:紫色是当前正在看的节点,蓝色是它的父节点,红色是正被检查奇偶的祖父节点,绿色表示这个节点已经被计入答案。现在当前和是 0。
5当前和 = 0走到节点 6。它是根,既没有父节点也没有祖父。没有祖父就谈不上计入,直接跳过,继续往下走。
6当前和 = 0走到节点 7。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
7当前和 = 0走到节点 12。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
8当前和 = 12祖父 6 是偶数,条件满足。把当前节点 12 加进答案,它变成绿色。当前和从 0 涨到 12。
9当前和 = 12走到节点 9。它的父节点是 12,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
10当前和 = 12祖父 7 是奇数,条件不满足。当前节点 9 不计入,它标红表示被排除。当前和保持 12 不变。
11当前和 = 12走到节点 5。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
12当前和 = 17祖父 6 是偶数,条件满足。把当前节点 5 加进答案,它变成绿色。当前和从 12 涨到 17。
13当前和 = 17走到节点 4。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
14当前和 = 17祖父 7 是奇数,条件不满足。当前节点 4 不计入,它标红表示被排除。当前和保持 17 不变。
15当前和 = 17走到节点 11。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
16当前和 = 17祖父 7 是奇数,条件不满足。当前节点 11 不计入,它标红表示被排除。当前和保持 17 不变。
17当前和 = 17左边以 7 为根的这一支处理完了。目前计入了 12 和 5,当前和 17。注意计入的都是「祖父是偶数 6」那一层的节点;它们下面的孩子祖父变成了奇数 7,所以全被跳过。接着看右边以 8 为根的这一支。
18当前和 = 17走到节点 8。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
19当前和 = 17走到节点 10。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
20当前和 = 27祖父 6 是偶数,条件满足。把当前节点 10 加进答案,它变成绿色。当前和从 17 涨到 27。
21当前和 = 27走到节点 3。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
22当前和 = 30祖父 6 是偶数,条件满足。把当前节点 3 加进答案,它变成绿色。当前和从 27 涨到 30。
23当前和 = 30走到节点 15。它的父节点是 3,祖父节点是 8。判定只看祖父:接下来检查祖父 8 是奇是偶。
24当前和 = 45祖父 8 是偶数,条件满足。把当前节点 15 加进答案,它变成绿色。当前和从 30 涨到 45。
25答案 = 45遍历结束,绿色的就是被选中的 5 个节点:12、5、10、3、15。它们的共同点是祖父的值都是偶数。把它们加起来:12 加 5 加 10 加 3 加 15,等于 45。
26答案 = 45回顾一下:12、5、10、3 的祖父都是根节点 6,6 是偶数,所以入选;15 的祖父是 8,8 也是偶数,入选。剩下的节点要么祖父是奇数 7,要么是根和根的孩子根本没有祖父,所以都没算进来。答案就是 45。

⚠️ 容易写错的地方

✗ 错：把判定条件看成「父节点是偶数」或「自己是偶数」

✓ 对：只看祖父节点的值是不是偶数

题目要的是隔两代的祖父,父节点和节点自身的奇偶都不影响是否计入

✗ 错：给根和根的孩子硬凑一个祖父

✓ 对：没有祖父的节点一律跳过

根没有父亲也没有祖父,根的孩子有父亲但没有祖父,这两层永远不计入

✗ 错：担心节点自身是奇数就不能计入

✓ 对：节点值是奇是偶都行,只要祖父是偶数就计入

比如祖父 6 偶数、节点 3 奇数,3 照样要加进答案

完整代码（Python / C++ / Java）

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;
    }
}

复杂度

时间

O(n)

n 是节点总数。每个节点在 DFS 里只被访问一次,访问时做的判断和累加都是常数操作,所以总时间和节点数成正比

空间

O(h)

额外空间是递归调用栈,峰值深度等于树高 h。树退化成一条链时 h 等于 n,最坏 O(n);树比较平衡时 h 约为以 2 为底 n 的对数。除递归栈外只用了几个变量

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着祖父节点值为偶数的节点和的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么递归时要额外把父节点、祖父节点的值往下传?+

判断一个节点要不要计入,需要知道它祖父的值,也就是往上看两层。可深度优先是自顶向下走的,真到了某个节点,上面两层的信息早就不在当前调用里了。所以把「父节点值、祖父节点值」做成递归参数一路带下去,到任意节点都能直接拿到祖父值,O(1) 完成判定,不用每次再往上回溯。

用广度优先的层序遍历能做吗?+

能。层序遍历时给每个节点额外记录它的父节点,出队时通过父节点再拿到祖父节点,同样能判定。不过那样要维护父指针映射,比深度优先直接带参数稍微繁琐一点,两者时间都是 O(n)。

参考代码为什么写成「父节点值是偶数就加孩子」,而不是直接看祖父?+

这是一个等价变形。站在某个节点 root 上,它的父节点值记作 x。如果 x 是偶数,那么 root 的两个孩子的祖父正好就是这个偶数的 x,所以把孩子加进答案。它和动画里「站在节点抬头看祖父」检查的是同一批节点对,只是观察的落脚点换了一层,答案完全一样。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把祖父节点值为偶数的节点和一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1315中等树 · BST

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

这道题到底在问什么

输入: root = [6,7,8,12,5,10,3,9,null,4,11,null,null,null,15]
输出: 45
输入: root = [1]
输出: 0

先想最直接的笨办法

最优解：一步一步想明白

3记牢一句:DFS 往下走时把父、祖父两个值带在手上,到每个节点抬头看祖父是不是偶数,是就把自己加进答案。下面每一帧都在套这个动作。
4当前和 = 0 · 待遍历先看清这棵树。一共 11 个节点,我们会用深度优先把它们一个一个走到。约定一下颜色:紫色是当前正在看的节点,蓝色是它的父节点,红色是正被检查奇偶的祖父节点,绿色表示这个节点已经被计入答案。现在当前和是 0。
5当前和 = 0走到节点 6。它是根,既没有父节点也没有祖父。没有祖父就谈不上计入,直接跳过,继续往下走。
6当前和 = 0走到节点 7。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
7当前和 = 0走到节点 12。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
8当前和 = 12祖父 6 是偶数,条件满足。把当前节点 12 加进答案,它变成绿色。当前和从 0 涨到 12。
9当前和 = 12走到节点 9。它的父节点是 12,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
10当前和 = 12祖父 7 是奇数,条件不满足。当前节点 9 不计入,它标红表示被排除。当前和保持 12 不变。
11当前和 = 12走到节点 5。它的父节点是 7,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
12当前和 = 17祖父 6 是偶数,条件满足。把当前节点 5 加进答案,它变成绿色。当前和从 12 涨到 17。
13当前和 = 17走到节点 4。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
14当前和 = 17祖父 7 是奇数,条件不满足。当前节点 4 不计入,它标红表示被排除。当前和保持 17 不变。
15当前和 = 17走到节点 11。它的父节点是 5,祖父节点是 7。判定只看祖父:接下来检查祖父 7 是奇是偶。
16当前和 = 17祖父 7 是奇数,条件不满足。当前节点 11 不计入,它标红表示被排除。当前和保持 17 不变。
17当前和 = 17左边以 7 为根的这一支处理完了。目前计入了 12 和 5,当前和 17。注意计入的都是「祖父是偶数 6」那一层的节点;它们下面的孩子祖父变成了奇数 7,所以全被跳过。接着看右边以 8 为根的这一支。
18当前和 = 17走到节点 8。它的父节点是 6,但再往上没有祖父了。没有祖父就谈不上计入,直接跳过,继续往下走。
19当前和 = 17走到节点 10。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
20当前和 = 27祖父 6 是偶数,条件满足。把当前节点 10 加进答案,它变成绿色。当前和从 17 涨到 27。
21当前和 = 27走到节点 3。它的父节点是 8,祖父节点是 6。判定只看祖父:接下来检查祖父 6 是奇是偶。
22当前和 = 30祖父 6 是偶数,条件满足。把当前节点 3 加进答案,它变成绿色。当前和从 27 涨到 30。
23当前和 = 30走到节点 15。它的父节点是 3,祖父节点是 8。判定只看祖父:接下来检查祖父 8 是奇是偶。
24当前和 = 45祖父 8 是偶数,条件满足。把当前节点 15 加进答案,它变成绿色。当前和从 30 涨到 45。
25答案 = 45遍历结束,绿色的就是被选中的 5 个节点:12、5、10、3、15。它们的共同点是祖父的值都是偶数。把它们加起来:12 加 5 加 10 加 3 加 15,等于 45。
26答案 = 45回顾一下:12、5、10、3 的祖父都是根节点 6,6 是偶数,所以入选;15 的祖父是 8,8 也是偶数,入选。剩下的节点要么祖父是奇数 7,要么是根和根的孩子根本没有祖父,所以都没算进来。答案就是 45。

⚠️ 容易写错的地方

✗ 错：把判定条件看成「父节点是偶数」或「自己是偶数」

✓ 对：只看祖父节点的值是不是偶数

题目要的是隔两代的祖父,父节点和节点自身的奇偶都不影响是否计入

✗ 错：给根和根的孩子硬凑一个祖父

✓ 对：没有祖父的节点一律跳过

根没有父亲也没有祖父,根的孩子有父亲但没有祖父,这两层永远不计入

✗ 错：担心节点自身是奇数就不能计入

✓ 对：节点值是奇是偶都行,只要祖父是偶数就计入

比如祖父 6 偶数、节点 3 奇数,3 照样要加进答案

完整代码（Python / C++ / Java）

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;
    }
}

复杂度

时间

O(n)

n 是节点总数。每个节点在 DFS 里只被访问一次,访问时做的判断和累加都是常数操作,所以总时间和节点数成正比

空间

O(h)

额外空间是递归调用栈,峰值深度等于树高 h。树退化成一条链时 h 等于 n,最坏 O(n);树比较平衡时 h 约为以 2 为底 n 的对数。除递归栈外只用了几个变量

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

为什么递归时要额外把父节点、祖父节点的值往下传?+

用广度优先的层序遍历能做吗?+

参考代码为什么写成「父节点值是偶数就加孩子」,而不是直接看祖父?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

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

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

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

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

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

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