原文链接: https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs

英文原文

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

 

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [1, 2^10].
• Each node's value is between [1, 100].
• 1 <= distance <= 10

中文题目

给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

 

示例 1：

 

输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。

示例 2：

输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。

示例 3：

输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出：1
解释：唯一的好叶子节点对是 [2,5] 。

示例 4：

输入：root = [100], distance = 1
输出：0

示例 5：

输入：root = [1,1,1], distance = 2
输出：1

 

提示：

• tree 的节点数在 [1, 2^10] 范围内。
• 每个节点的值都在 [1, 100] 之间。
• 1 <= distance <= 10

通过代码

高赞题解

思路

1. root->val 没用，父节点和子节点的距离是 $1$
2. 对树后序遍历 ，需要返回这个节点到其下方所有叶子节点的距离
3. 这样就可以将这个节点的左子树所有叶子节点和右子树所有叶子节点都凑个对
4. 然后将所有叶子节点不超过距离的弄到一起返回

图解

<,,,>

答题

[]
class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        int ans = 0;
        dfs(root, distance, ans);
        return ans;
    }

    vector<int> dfs(TreeNode* root, int distance, int& ans) {
        if (root == nullptr) return {};
        if (root->left == nullptr && root->right == nullptr) return { 0 };

        vector<int> ret;
        auto left = dfs(root->left, distance, ans);
        for (auto& e : left) {
            if (++e > distance) continue;
            ret.push_back(e);
        }
        auto right = dfs(root->right, distance, ans);
        for (auto& e : right) {
            if (++e > distance) continue;
            ret.push_back(e);
        }

        for (auto l : left) {
            for (auto r : right) {
                ans += (l + r <= distance);
            }
        }

        return ret;
    }
};

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

统计信息

通过次数	提交次数	AC比率
8983	15741	57.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言