[leetcode] 1530. Number of Good Leaf Nodes Pairs

[leetcode] 1530. Number of Good Leaf Nodes Pairs

Description

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 = 3Output: 1Explanation: 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 = 3Output: 2Explanation: 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 = 3Output: 1Explanation: The only good pair is [2,5].

Example 4:

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

Example 5:

Input: root = [1,1,1], distance = 2Output: 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

分析

题目的意思是：给定二叉树，找出二叉树两叶子结点小于或等于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 = rightclass Solution: def solve(self,root,distance): if(root is None): return [] if(root.left==root.right): return [1] l_list=self.solve(root.left,distance) r_list=self.solve(root.right,distance) for l in l_list: for r in r_list: if(l+r<=distance): self.res+=1 return [item+1 for item in l_list+r_list] def countPairs(self, root: TreeNode, distance: int) -> int: self.res=0 self.solve(root,distance) return self.res

参考文献

​​[LeetCode] [Python] Clean DFS Solution with Video Explanation​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。