题目描述
思路解析
一句话答案：LeetCode 1530 好叶子节点对的数量：一次后序遍历，每个节点上交一份到各叶子距离的清单，在节点处把左右两支按距离配对，两段距离够近就是一对好叶子，时间 O(n·d²)。
什么样的两片叶子算一组「好对」
叶子就是没有左右孩子的节点。给一棵二叉树和整数 distance，数有多少对叶子，两片间的最短路径长度不超过 distance——路径长度就是两叶子间的边数。用题面这棵树：根 50，左边挂 30、下面是叶子 10 和 40；右边挂 70，下面是叶子 60 和节点 80，80 再挂叶子 90。distance = 3。
两两枚举叶子对，规模一大就撑不住
两个叶子间的路径形状固定：先各自往上爬到最近公共祖先，也就是两片叶子最靠下的共同祖先，再分头下去，路径长度就等于两叶子到祖先的距离之和。照定义硬做，就得把叶子两两配对、各求一次祖先算长度；上千节点的树叶子成百上千，配对数平方级，撑不住。
每对好叶子只在它们的公共祖先处数一次
既然每对叶子都在公共祖先处才第一次分到左右两边，就反过来站在每个节点上只数「路径恰好在这里拐弯」的对——它必然一片来自左子树、一片来自右子树。为知道子树里每个叶子离自己多远，每个节点维护一个距离桶，也就是按到当前节点的距离分组的计数，cnt[d] 是到当前节点距离为 d 的叶子个数。用后序遍历，轮到某节点时左右孩子的桶都已算好。
每个节点先配对、再把距离加一上交
叶子到自己距离 0，桶就是 cnt[0]=1。非叶节点先递归拿到左桶 left、右桶 right。先配对：left[i] 是到左孩子距离 i 的叶子数，到本节点变 i+1，右支同理 j+1，经过本节点的路径长是 i+j+2；只要 i+j+2 ≤ distance，就把 left[i] 乘 right[j] 加进答案。
再把两支的桶各自距离加 1，cnt[d+1] = left[d] + right[d]，交给父亲。这里两处顺序要盯紧：配对必须在合并前，否则合成一份就分不清叶子来自哪支、会错配；上交时每个距离别忘加 1，忘了父节点算出的路径偏短，把太远的对误判成好对。
题面这棵树，答案 2 是怎么数出来的
后序从根 50 下探到最左叶子。叶子 10 和 40 各返回「距离 0 处 1 个」。回到父亲 30，左右两支都是距离 0，经过 30 的路径长 0+0+2=2 ≤ 3，配成一对、答案记 1；合并后 30 的桶是「距离 1 处 2 个」。
右边叶子 60 返回「距离 0 处 1 个」；节点 80 只挂孩子 90、不配对，上交后桶是「距离 1 处 1 个」。到节点 70，左孩子那支距离 0、右孩子那支距离 1，路径长 0+1+2=3 ≤ 3，再配一对、答案累到 2。回到根 50，叶子到 50 是距离 2、2、3，任意一对最短也 4、超 3。答案 2：10 配 40，60 配 90。
为什么它几乎是线性的，还有哪些坑
桶最多 distance+1 项。每节点做一次 distance 乘 distance 的配对，全树 O(n·d²)，d 就是 distance、不超过 10，近乎线性。空间 O(h·d)，h 是树高、最坏成链时等于 n。边界看两种：单个节点没有第二片叶子、答案 0；两叶子在根下分叉、路径长 2，distance 给 2 算一对、给 1 不成，卡点是小于等于。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句话: 每个节点向上交一份「子树里各叶子到我距离几、各有几个」的清单; 在每个节点, 把左支的距离和右支的距离相加, 只要和不超过 distance 就配成好对; 上交给父亲时清单里所有距离再加 1。下面每一帧都在套这条规则。
总览 · 树与四个叶子：先看清这棵树。根是节点 50。它左边挂节点 30, 30 下面是两个叶子 10 和 40; 它右边挂节点 70, 70 下面一个是叶子 60, 另一个是节点 80, 80 再往下才是叶子 90。紫色点亮的四个就是叶子: 10、40、60、90。我们要数的是: 这四个叶子里, 有多少对彼此路径长度不超过 3。
规则 · 每个节点返回什么：把规则在画面上钉死。每个节点要向上交一份清单, 记录它子树里每个叶子到这个节点的距离, 以及每种距离上各有几个叶子。叶子最简单, 它到自己距离是 0, 清单就是「距离 0 处 1 个叶子」。等这份清单交给父亲时, 因为又往上走了一条边, 清单里每个距离都要加 1。
规则 · 配对在哪发生：再钉死第二条: 配对只在每个节点的左右两支之间发生。站在一个节点上, 把左孩子那一支某个距离的叶子, 和右孩子那一支某个距离的叶子相加, 如果两段距离之和不超过 distance, 它们就配成好对, 配对数等于两个距离上叶子个数相乘。为什么这样不重不漏? 因为任意两个叶子, 一定在它们最近的公共祖先那里第一次分到左右两支, 就在那个节点被数到一次。
下行 · 进入节点 50：走到节点 50, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 30 和 70, 按后序先一路往下探。
下行 · 进入节点 30：走到节点 30, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 10 和 40, 按后序先一路往下探。
下行 · 到叶子 10：往下走到叶子 10, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
结算 · 叶子 10 清单：结算叶子 10, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 10 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
下行 · 到叶子 40：往下走到叶子 40, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
结算 · 叶子 40 清单：结算叶子 40, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 40 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
配对 · 在节点 30：回到节点 30, 它的左右两支清单都齐了。左支是 距离1处 1 个(叶子 10); 右支是 距离1处 1 个(叶子 40)。把左右距离两两相加看谁不超过 3: 距离1的 10 配 距离1的 40(1+1=2 ≤ 3)。绿色高亮的就是这一对好叶子。ans 加上 1, 现在是 1。
结算 · 子树 30 清单：结算节点 30, 它变绿。把左右两支已经加过 1 的清单合并, 子树 30 的清单是 距离1处 2 个(叶子 10、40)。它再上交给父亲, 父亲会把每个距离继续加 1。
下行 · 进入节点 70：走到节点 70, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 60 和 80, 按后序先一路往下探。
下行 · 到叶子 60：往下走到叶子 60, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
结算 · 叶子 60 清单：结算叶子 60, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 60 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
下行 · 进入节点 80：走到节点 80, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 90, 按后序先一路往下探。
下行 · 到叶子 90：往下走到叶子 90, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
结算 · 叶子 90 清单：结算叶子 90, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 90 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
直传 · 节点 80 只有一支：节点 80 只挂着一个孩子, 凑不出跨左右两支的叶子对, 所以这里不配对。它把这一支的叶子清单 距离1处 1 个(叶子 90) 原样往上交, 父亲收到再把距离加 1。
结算 · 子树 80 清单：结算节点 80, 它变绿。把左右两支已经加过 1 的清单合并, 子树 80 的清单是 距离1处 1 个(叶子 90)。它再上交给父亲, 父亲会把每个距离继续加 1。
配对 · 在节点 70：回到节点 70, 它的左右两支清单都齐了。左支是 距离1处 1 个(叶子 60); 右支是 距离2处 1 个(叶子 90)。把左右距离两两相加看谁不超过 3: 距离1的 60 配 距离2的 90(1+2=3 ≤ 3)。绿色高亮的就是这一对好叶子。ans 加上 1, 现在是 2。
结算 · 子树 70 清单：结算节点 70, 它变绿。把左右两支已经加过 1 的清单合并, 子树 70 的清单是 距离1处 1 个(叶子 60); 距离2处 1 个(叶子 90)。它再上交给父亲, 父亲会把每个距离继续加 1。
配对 · 在节点 50：回到节点 50, 左支是 距离2处 2 个(叶子 10、40); 右支是 距离2处 1 个(叶子 60); 距离3处 1 个(叶子 90)。把左右距离两两相加: 2+2=4, 2+3=5。每一种组合的距离之和都超过 3, 所以在根这里一对都配不成, 标红的这几个叶子隔得太远。ans 保持 2。
结算 · 子树 50 清单：结算根 50, 它变绿, 整棵树搜完了。把所有节点配出的好对加起来, ans 就是 2: 一组是节点 30 配出的 10 和 40, 一组是节点 70 配出的 60 和 90。这就是答案。
回放 · 两组好叶子对：回放一遍。整个过程只做了一次后序遍历: 从根下探到每个叶子, 再自底向上, 在每个节点把左右两支的叶子按距离配对。节点 30 把距离都是 1 的叶子 10 和 40 配成一对, 路径长度 2; 节点 70 把距离 1 的叶子 60 和距离 2 的叶子 90 配成一对, 路径长度 3。根 50 想跨左右两支再配, 但都隔得太远。最终好叶子对是 2 组。
对比 · 为什么根上配不成：看最容易绕晕的一处。叶子 10 和叶子 60 分属根的左右两支, 它们要会合必须爬到根 50。10 到根距离 2, 60 到根距离 2, 路径就是 2 加 2 等于 4, 已经超过 3。叶子 90 离根更远, 距离 3, 配谁都更超。所以一对叶子越是要绕到高处的祖先才会合, 路径就越长, 这也是为什么每对叶子只在它们最近的那个公共祖先处被数一次。
边界看三种: 只有一个节点时没有第二个叶子, 答案 0; 两个叶子在根下分叉、路径长度 2, distance 给 2 就算一组、给 1 就配不成。距离的临界点要看清是小于等于。
面试重点: 返回完整距离清单才能让父层正确配对, 但清单被 distance 截断所以很短; distance 是小常数, 整体接近线性; 配对必须在左右合并之前做, 否则分不清左右支会错配。
参考代码
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 countPairs(self, root: TreeNode, distance: int) -> int: self.ans = 0 # 返回 cnt: 长度 distance+1 的列表, cnt[d] = 子树里到当前节点距离为 d 的叶子个数 def dfs(node): cnt = [0] * (distance + 1) if node is None: return cnt if node.left is None and node.right is None: cnt[0] = 1 return cnt left = dfs(node.left) right = dfs(node.right) # 合并前先配对: 左支到左孩子距离 i → 到本节点 i+1; 右支同理 j+1 for i in range(distance + 1): for j in range(distance + 1): if i + j + 2 <= distance: self.ans += left[i] * right[j] # 合并: 左右两支距离各加 1, 上交给父亲 for d in range(distance): cnt[d + 1] = left[d] + right[d] return cnt dfs(root) return self.ans复杂度
- 时间：O(n · d²)，d 是 distance, 这道题里不超过 10。每个叶子的距离都被限制在 1 到 d 之间, 每个节点维护的距离清单最多 d 项; 在每个节点做一次最多 d 乘 d 的配对双循环, 全树 n 个节点合起来是 O(n · d²)。因为 d 是不超过 10 的小常数, 实际接近线性
- 空间：O(h · d)，按峰值算: 后序递归的栈深是树高 h, 最坏退化成长链时 h 等于 n; 递归路径上每一层都挂着一份最多 d 项的距离清单, 所以同时存活的清单总量是 O(h · d)。距离清单本身每份是 O(d)
易错点
面试追问把动画讲成自己的话
追问为什么每个节点要返回完整的距离清单, 只返回最近那个叶子的距离行不行?
追问节点数可以到一千多, distance 到十, 这个做法会不会太慢?
追问为什么配对一定要在左右清单合并之前做?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
奇偶树
LeetCode 1609 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题