好叶子节点对的数量 图解题解

什么样的两片叶子算一组「好对」

叶子就是没有左右孩子的节点。给一棵二叉树和整数 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 不成，卡点是小于等于。

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

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 ans = 0;
    int dist = 0;

    int countPairs(TreeNode* root, int distance) {
        dist = distance;
        dfs(root);
        return ans;
    }

    // 返回 cnt: 长度 dist+1, cnt[d] = 子树里到当前节点距离为 d 的叶子个数
    vector<int> dfs(TreeNode* node) {
        vector<int> cnt(dist + 1, 0);
        if (!node) return cnt;
        if (!node->left && !node->right) {
            cnt[0] = 1;
            return cnt;
        }
        vector<int> left = dfs(node->left);
        vector<int> right = dfs(node->right);
        // 合并前先配对: 左支到左孩子距离 i → 到本节点 i+1; 右支同理 j+1
        for (int i = 0; i <= dist; ++i) {
            for (int j = 0; j <= dist; ++j) {
                if (i + j + 2 <= dist) {
                    ans += left[i] * right[j];
                }
            }
        }
        // 合并: 左右两支距离各加 1, 上交给父亲
        for (int d = 0; d < dist; ++d) {
            cnt[d + 1] = left[d] + right[d];
        }
        return cnt;
    }
};

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 {
    int ans = 0;
    int dist = 0;

    public int countPairs(TreeNode root, int distance) {
        dist = distance;
        dfs(root);
        return ans;
    }

    // 返回 cnt: 长度 dist+1, cnt[d] = 子树里到当前节点距离为 d 的叶子个数
    int[] dfs(TreeNode node) {
        int[] cnt = new int[dist + 1];
        if (node == null) {
            return cnt;
        }
        if (node.left == null && node.right == null) {
            cnt[0] = 1;
            return cnt;
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        // 合并前先配对: 左支到左孩子距离 i → 到本节点 i+1; 右支同理 j+1
        for (int i = 0; i <= dist; ++i) {
            for (int j = 0; j <= dist; ++j) {
                if (i + j + 2 <= dist) {
                    ans += left[i] * right[j];
                }
            }
        }
        // 合并: 左右两支距离各加 1, 上交给父亲
        for (int d = 0; d < dist; ++d) {
            cnt[d + 1] = left[d] + right[d];
        }
        return cnt;
    }
}