JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-06-20
目录

好叶子节点对的数量Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你二叉树的根节点 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

# 思路

   求每一个节点,左右子树里,叶子节点之间距离<=distance的组合数目,接着递归向上
   不会重复,因为每个节点的左右子组合都是不一样的,所以让左的数目*右的数目求出组合数

# 解法


/**
 * 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;
 *     }
 * }
 */
 /*
 *   求每一个节点,左右子树里,叶子节点之间距离<=distance的组合数目,接着递归向上
 *   不会重复,因为每个节点的左右子组合都是不一样的,所以让左的数目*右的数目求出组合数
 */
class Solution {
    private int ans = 0;
    public int countPairs(TreeNode root, int distance) {
        dfs(root, distance);
        return ans;
    }
    //自底向上的递归,用count数组统计和当前节点的距离为 i 的叶子节点数目,
    //多于distance的不用考虑
    public int[] dfs(TreeNode root, int distance){
        if(root == null){
            return new int[distance+1];
        }
        int[] count = new int[distance+1];
        if(root.left==null && root.right==null){
            count[1] = 1;
            return count;
        }
        int[] leftCount = dfs(root.left, distance);
        int[] rightCount = dfs(root.right, distance);
        //计算组合数
        for(int i=1; i<=distance; i++){
            for(int j=1; j<=distance-i; j++){
                ans += leftCount[i]*rightCount[j];
            }
        }
        //向上层返回,距离+1
        for(int i=2; i<=distance; i++){
            count[i] = leftCount[i-1]+rightCount[i-1];
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1633. 各赛事的用户注册率 Java
07-02
02
1636. 按照频率将数组升序排序 Java
07-02
03
1639. 通过给定词典构造目标字符串的方案数 Java
07-02
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式