X

LEETCODE 1530. 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1530

解题思路分析:

对于二叉树问题,首先我们需要明确两点:

  1. 二叉树的叶子节点数量是一定的。
  2. 对于任意两个叶子节点,他们可能会存在一个或多个公共祖先,如果这两个叶子节点间的连线必须通过某一个公共祖先的话,那么符合条件的连线只有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-解题思路分析/
Categories: leetcode
kwantong: