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

这道题到底在问什么

输入

叶子 10 和 40, 在节点 30 下面分叉

输出

路径 10-30-40 长度 2, 不超过 3, 是一组好对

输入

叶子 60 和 90, 在节点 70 下面分叉

输出

路径 60-70-80-90 长度 3, 不超过 3, 是一组好对

输入

叶子 10 和 60, 要绕到根 50 才会合

输出

路径长度 4, 超过 3, 不是好对

最优解：一步一步想明白

1. 3记牢一句话: 每个节点向上交一份「子树里各叶子到我距离几、各有几个」的清单; 在每个节点, 把左支的距离和右支的距离相加, 只要和不超过 distance 就配成好对; 上交给父亲时清单里所有距离再加 1。下面每一帧都在套这条规则。
2. 4根 50, 叶子是 10 40 60 90先看清这棵树。根是节点 50。它左边挂节点 30, 30 下面是两个叶子 10 和 40; 它右边挂节点 70, 70 下面一个是叶子 60, 另一个是节点 80, 80 再往下才是叶子 90。紫色点亮的四个就是叶子: 10、40、60、90。我们要数的是: 这四个叶子里, 有多少对彼此路径长度不超过 3。
3. 5返回「子树里各叶子到我距离几、各几个」把规则在画面上钉死。每个节点要向上交一份清单, 记录它子树里每个叶子到这个节点的距离, 以及每种距离上各有几个叶子。叶子最简单, 它到自己距离是 0, 清单就是「距离 0 处 1 个叶子」。等这份清单交给父亲时, 因为又往上走了一条边, 清单里每个距离都要加 1。
4. 6在每个节点配对左右两支的叶子再钉死第二条: 配对只在每个节点的左右两支之间发生。站在一个节点上, 把左孩子那一支某个距离的叶子, 和右孩子那一支某个距离的叶子相加, 如果两段距离之和不超过 distance, 它们就配成好对, 配对数等于两个距离上叶子个数相乘。为什么这样不重不漏? 因为任意两个叶子, 一定在它们最近的公共祖先那里第一次分到左右两支, 就在那个节点被数到一次。
5. 7进入 50, 先把孩子算完走到节点 50, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 30 和 70, 按后序先一路往下探。
6. 8进入 30, 先把孩子算完走到节点 30, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 10 和 40, 按后序先一路往下探。
7. 9叶子 10, 准备结算往下走到叶子 10, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
8. 10叶子 10 返回 距离0处 1 个结算叶子 10, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 10 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
9. 11叶子 40, 准备结算往下走到叶子 40, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
10. 12叶子 40 返回 距离0处 1 个结算叶子 40, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 40 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
11. 13配成 1 对, ans 到 1回到节点 30, 它的左右两支清单都齐了。左支是 距离1处 1 个(叶子 10); 右支是 距离1处 1 个(叶子 40)。把左右距离两两相加看谁不超过 3: 距离1的 10 配 距离1的 40(1+1=2 ≤ 3)。绿色高亮的就是这一对好叶子。ans 加上 1, 现在是 1。
12. 14节点 30 上交 距离1处 2 个(叶子 10、40)结算节点 30, 它变绿。把左右两支已经加过 1 的清单合并, 子树 30 的清单是 距离1处 2 个(叶子 10、40)。它再上交给父亲, 父亲会把每个距离继续加 1。
13. 15进入 70, 先把孩子算完走到节点 70, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 60 和 80, 按后序先一路往下探。
14. 16叶子 60, 准备结算往下走到叶子 60, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
15. 17叶子 60 返回 距离0处 1 个结算叶子 60, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 60 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
16. 18进入 80, 先把孩子算完走到节点 80, 蓝色表示它已经进入搜索路径, 但还没结算, 因为得先把孩子那边收完。它下面挂着 90, 按后序先一路往下探。
17. 19叶子 90, 准备结算往下走到叶子 90, 紫色表示正看着它。它没有左右孩子, 是个叶子, 可以马上结算。
18. 20叶子 90 返回 距离0处 1 个结算叶子 90, 它变绿。它到自己的距离是 0, 所以这份清单是「距离 0 处 1 个叶子, 就是 90 自己」。它把这份清单交给父亲, 父亲收到后会把这个 0 加成 1。
19. 21单支, 不配对, 清单直接上交节点 80 只挂着一个孩子, 凑不出跨左右两支的叶子对, 所以这里不配对。它把这一支的叶子清单 距离1处 1 个(叶子 90) 原样往上交, 父亲收到再把距离加 1。
20. 22节点 80 上交 距离1处 1 个(叶子 90)结算节点 80, 它变绿。把左右两支已经加过 1 的清单合并, 子树 80 的清单是 距离1处 1 个(叶子 90)。它再上交给父亲, 父亲会把每个距离继续加 1。
21. 23配成 1 对, ans 到 2回到节点 70, 它的左右两支清单都齐了。左支是 距离1处 1 个(叶子 60); 右支是 距离2处 1 个(叶子 90)。把左右距离两两相加看谁不超过 3: 距离1的 60 配 距离2的 90(1+2=3 ≤ 3)。绿色高亮的就是这一对好叶子。ans 加上 1, 现在是 2。
22. 24节点 70 上交 距离1处 1 个(叶子 60); 距离2处 1 个(叶子 90)结算节点 70, 它变绿。把左右两支已经加过 1 的清单合并, 子树 70 的清单是 距离1处 1 个(叶子 60); 距离2处 1 个(叶子 90)。它再上交给父亲, 父亲会把每个距离继续加 1。
23. 25两支都太远, 配不成回到节点 50, 左支是 距离2处 2 个(叶子 10、40); 右支是 距离2处 1 个(叶子 60); 距离3处 1 个(叶子 90)。把左右距离两两相加: 2+2=4, 2+3=5。每一种组合的距离之和都超过 3, 所以在根这里一对都配不成, 标红的这几个叶子隔得太远。ans 保持 2。
24. 26整棵树搜完, ans = 2结算根 50, 它变绿, 整棵树搜完了。把所有节点配出的好对加起来, ans 就是 2: 一组是节点 30 配出的 10 和 40, 一组是节点 70 配出的 60 和 90。这就是答案。
25. 27ans = 2(10配40, 60配90)回放一遍。整个过程只做了一次后序遍历: 从根下探到每个叶子, 再自底向上, 在每个节点把左右两支的叶子按距离配对。节点 30 把距离都是 1 的叶子 10 和 40 配成一对, 路径长度 2; 节点 70 把距离 1 的叶子 60 和距离 2 的叶子 90 配成一对, 路径长度 3。根 50 想跨左右两支再配, 但都隔得太远。最终好叶子对是 2 组。
26. 28左右都在距离 2 往上, 和必超 3看最容易绕晕的一处。叶子 10 和叶子 60 分属根的左右两支, 它们要会合必须爬到根 50。10 到根距离 2, 60 到根距离 2, 路径就是 2 加 2 等于 4, 已经超过 3。叶子 90 离根更远, 距离 3, 配谁都更超。所以一对叶子越是要绕到高处的祖先才会合, 路径就越长, 这也是为什么每对叶子只在它们最近的那个公共祖先处被数一次。

⚠️ 容易写错的地方

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

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

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

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

复杂度

面试官可能追问