5474. 好叶子节点对的数量 [medium]
5474. 好叶子节点对的数量 [medium]
https://leetcode-cn.com/contest/weekly-contest-199/problems/number-of-good-leaf-nodes-pairs/
给你二叉树的根节点 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
First Try
2020-07-26
看到tree的节点数在2^10的范围，感觉递归的O(N)算法很难通过了，但还是尝试按照递归常规写法来一边。
在如何筛选已经无效的距离，并且在左右子节点的笛卡尔积中进行快速筛选，都没有什么高效的思路。只能按照最基础的O(M * M)进行遍历筛选。
感觉肯定是超时了，结果一提交，竟然又通过了。。。
于是周赛又解决了一道题。
递归的思路是左边的n个叶子节点的距离的列表，右边的n个叶子节点的距离的列表，然后对两者进行筛选，去除已经明确大于distance的无效的元素，然后进行笛卡尔积式的两轮遍历，找到a + b <= distance的所有点，然后用于下一个父级节点的左/右节点的返回项。在这些操作过程中统计次数就行。
# 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
import heapq
class Solution:
def countPairs(self, root: TreeNode, distance: int) -> int:
# 不知道O(N)算法能否通过啊，节点数也太多了
rv = {"val": 0}
def col(node, target):
if not node:
return []
if not (node.left or node.right):
return [0]
left = col(node.left, target)
left = [l + 1 for l in left if (l + 1) < target]
right = col(node.right, target)
right = [r + 1 for r in right if (r + 1) < target]
if not (len(left) or len(right)):
return []
if (not len(left)) or (not len(right)):
return left + right
for l in left:
for r in right:
if l + r <= target:
rv["val"] += 1
return left + right
col(root, distance)
return rv["val"]