【二叉树-中等】1530. 好叶子节点对的数量

【题目】
提示：

tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10
1
2
3

1. 注意此题根据提示可以知道，不同的节点可能具有相同的数值，所以不能仅仅凭借结点的数值就判断两个节点是否是同一个节点。
2. 思路：一看到这种路径距离第一反应就是最近公共父节点
   【代码】
   

# 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
class Solution:
    def dfs(self,root):
        if not root:return 
        self.path.append(root)
        if not root.left and not root.right:
            self.leaf_path.append(self.path[:])
        self.dfs(root.left)
        self.dfs(root.right)
        self.path.pop()
    def countPairs(self, root: TreeNode, distance: int) -> int:
        self.path=[]
        self.leaf_path=[]
        self.dfs(root)
        cnt=0
        for i in range(len(self.leaf_path)):
            for j in range(i+1,len(self.leaf_path)):
                item_i=self.leaf_path[i]
                item_j=self.leaf_path[j]
                idx=0
                for x,y in zip(item_i,item_j):
                    if x!=y:
                        break
                    idx+=1
                if (len(item_i)+len(item_j)-2*idx)<=distance:
                    cnt+=1
        return cnt
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