好叶子节点对的数量
给你二叉树的根节点 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1530
解题思路分析：
对于二叉树问题，首先我们需要明确两点：
- 二叉树的叶子节点数量是一定的。
- 对于任意两个叶子节点，他们可能会存在一个或多个公共祖先，如果这两个叶子节点间的连线必须通过某一个公共祖先的话，那么符合条件的连线只有1条。
解题时，我们使用dfs递归方式遍历每一个节点，递归方法的参数包含当前节点，以及当前节点所在的层数（根节点的层数默认为0）。递归方法的返回值为，当前节点下所有叶子节点所在层数的集合。递归时，如果当前节点为空，返回一个空集合。如果当前节点为叶子节点，那么返回当前节点所在的层数。剩下的情况即是当前节点为非叶子节点，我们使用dfs递归方式分别得到左子树下所有叶子节点所在的层数集合left，并且获得右子树下所有叶子节点所在的层数集合right。此时，我们可以暴力查看left中每个叶子节点到right中每个叶子节点的距离，这个距离的计算方法为：left中的一个叶子节点的层数减去当前层数，加上right中的层数减去当前层数。如果该距离小于等于distance，返回结果加一。递归方法的最后将left和right合并后，作为返回值返回给上一层递归。
实现代码：
int count=0; // 返回结果
public int countPairs(TreeNode root, int distance) {
help(root,distance,0); // dfs递归查看每个通过每个节点的连线
return count;
}
// root：当前节点
// distance：题目给出的距离
// level：当前节点所在层数
// 返回值：当前节点下所有叶子节点所在层数集合
List<Integer> help(TreeNode root, int distance, int level){
if(root==null){ // 当前节点为空，返回空集合
return new ArrayList<>();
}
// 当前节点为叶子节点
if(root.left==null&&root.right==null){
// 返回当前节点所在层数
List<Integer> list=new ArrayList<>();
list.add(level);
return list;
}
// 左子树所有叶子节点所在层数集合
List<Integer> left=help(root.left, distance,level+1);
// 右子树所有叶子节点所在层数集合
List<Integer> right=help(root.right,distance,level+1);
// 查看通过当前节点的路径中，符合条件的个数
for(int l : left){
for(int r : right){
if((l-level)+(r-level)<=distance){
count++;
}
}
}
left.addAll(right); // 将左右两个集合合并后返回
return left;
} 本题解法执行时间为46ms。
Runtime: 46 ms, faster than 16.67% of Java online submissions for Number of Good Leaf Nodes Pairs.
Memory Usage: 52.1 MB, less than 100.00% of Java online submissions for Number of Good Leaf Nodes Pairs.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1530-number-of-good-leaf-nodes-pairs-解题思路分析/