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
}