1530.md

1530. Number of Good Leaf Nodes Pairs

Leetcode link

题目简介

本题给了我们两个参数，第一个 root 代表了二叉树的根结点、第二个 distance 代表了距离（距离由两个节点要经过多少节点才能相遇决定）

题目要求我们找出树的所有叶子节点中，相遇的距离小于 distance 有几对

解题思路

本题是一个树相关的题目，要求找树的叶子节点的距离我们可以使用 DFS 来遍历整棵树

但是问题是，我们怎么在遍历的过程中，把叶子节点直接的距离也一起计算出来呢？

方式有很多种，我在这里选择了用数组来记录

我构建了一个数组 leafDistances，数组记录的是以该节点为根结点，它到所有它的叶子节点的距离

假设今天有一棵树：

a
|	\
b  c

// leafDistances = [1, 1]

当我们构建了一个这样的数组的时候，我们就可以对数组中每个叶子节点的距离进行相加比较了

举个上面的例子，b 到 c 的距离就是 leafDistances[0] + leafDistances[1] 只要他们小于 distance，就可以给结果加一了

那么我们的问题就变成了，要怎么构造这个数组呢？分成两种情况：

1. 遍历叶子节点时：要返回 [1]，代表叶子节点的父节点到叶子节点的距离为 1
2. 遍历到父节点时：构建一个新的数组，把改节点左右两个子节点记录的数组距离都加一后 push 进新数组后返回

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} distance
 * @return {number}
 */
var countPairs = function(root, distance) {
    let result = 0;

    function dfs(node) {
        if(!node) return [];
      	// 遍历到叶子节点的情况
        if(!node.left && !node.right) return [1];

        const leftDistances = dfs(node.left);
        const rightDistances = dfs(node.right);

        // 每遍历到一个节点，找找经过当前节点的叶子节点有没有距离小于 distance 的其他叶子节点，如果有则记录下来
        for(const leftDistance of leftDistances) {
            for(const rightDistance of rightDistances) {
                if(leftDistance + rightDistance <= distance) {
                    result++;
                }
            }
        }

        // 每一个节点都有一个 leafDistances 数组
        // 数组的长度代表该节点有多少叶子节点，数组的值代表了改节点到某一个叶子节点的距离
        const leafDistances = [];
        // 处理一下要返回给上一个节点的数组（具体来说就是把距离+1）
        for(const ld of leftDistances) leafDistances.push(ld+1);
        for(const rd of rightDistances) leafDistances.push(rd+1);

        return leafDistances;
    }

    dfs(root);
    return result;
    
};