1530. Number of Good Leaf Nodes Pairs
给你一棵二元树
二个叶子节点间的最短距离如果小于distance就是good pairs
请问有几组good pairs
思路:
一开始原本想说用lca去找
就是找出所有叶子，并且纪录全部node的深度
然后在每组叶子组合去找lca
这样他们的最短距离就会是2个叶子的深度-2*lca的深度
不过会超时，G8
后来换个做法
如果有两个叶子刚好在一个node的左右边，那这个node就是这两个叶子的lca
所以就用leafL、leafR两个矩阵去纪录node左右两边的叶子离这个node多远
接着就去对每个node的leafR、leafL去数符合条件的数目
就可以得到答案了
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countPairs(root *TreeNode, distance int) int {
var dfs func(node *TreeNode) ([]int, int)
dfs = func(node *TreeNode) ([]int, int) {
if node == nil {
return []int{}, 0
}
if node.Right == nil && node.Left == nil {
return []int{1}, 0
}
leafl, cntl := dfs(node.Left)
leafr, cntr := dfs(node.Right)
cnt := cntl + cntr
n, m := len(leafl), len(leafr)
leaf := make([]int, 0, len(leafl)+len(leafr))
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if leafl[i]+leafr[j] <= distance {
cnt++
}
}
}
for _, val := range leafl {
if val < 9 {
leaf = append(leaf, val+1)
}
}
for _, val := range leafr {
if val < 9 {
leaf = append(leaf, val+1)
}
}
return leaf, cnt
}
_, cnt := dfs(root)
return cnt
}