1530_好叶子节点对的数量

类型：树

• 1530. 好叶子节点对的数量 💛

  https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs/

  这是字节面试的原题。

  ❓ 给你二叉树的根节点 root 和一个整数 distance 。

  如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。

  返回树中 好叶子节点对的数量 。

  💡 递归

  其实任意两个叶子结点之间，有且仅有一条最短路径，就是经过最近公共祖先 P 的那条。

  于是，我们枚举所有非叶子结点 P 作为公共祖先，找到以 P 为最近公共祖先的所有叶子结点对，计算每一对之间的距离，统计距离不超过 distance 的结点对数量。

  由于题目约束 distance ≤ 10，因此对于每一个非叶子结点 P，我们都开辟一个初度为 distance + 1 的数组 depths，其中 depths[i] 表示与 P 之间距离为 i 的叶子结点数目。

  class Solution:
      def countPairs(self, root: TreeNode, distance: int) -> int:
          # 对于 dfs(root,distance)，同时返回：
          # 每个叶子节点与 root 之间的距离
          # 以 root 为根节点的子树中好叶子节点对的数量
          def dfs(root: TreeNode, distance: int) -> (List[int], int):
              depths = [0] * (distance + 1)
              isLeaf = not root.left and not root.right
              if isLeaf:
                  depths[0] = 1
                  return (depths, 0)
  
              leftDepths, rightDepths = [0] * (distance + 1), [0] * (distance + 1)
              leftCount = rightCount = 0
  
              if root.left:
                  leftDepths, leftCount = dfs(root.left, distance)
              if root.right:
                  rightDepths, rightCount = dfs(root.right, distance)
  
              for i in range(distance):
                  depths[i + 1] += leftDepths[i]
                  depths[i + 1] += rightDepths[i]
  
              cnt = 0
              for i in range(distance + 1):
                  for j in range(distance - i - 1):
                      cnt += leftDepths[i] * rightDepths[j]
  
              return (depths, cnt + leftCount + rightCount)
  
  
          _, ret = dfs(root, distance)
          return ret

  时间复杂度：O(n * distance^2)，n 为结点数。空间复杂度：O(h * distance)，h 为树高度。