题目描述
思路解析动画文字版
记牢一句话: 每个节点向上交一份「子树里各叶子到我距离几、各有几个」的清单; 在每个节点, 把左支的距离和右支的距离相加, 只要和不超过 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题