作者Rushia (早瀬ユウカの体操服 )
標題Re: [閒聊] 每日leetcode
時間2024-07-18 18:27:30
※ 引述《oin1104 (是oin的說)》之銘言：
: 題目 :
: 給你叫做root的樹
: 還有distance
: 問你樹上所有的兩個葉子之間
: 在樹上的距離小於等於distance
: 的組合有多少
思路:
1.dfs這個樹紀錄葉子節點的深度，然後對左右的深度到root計算距離有沒有超過
有的話res就+1，然後把當前的左右葉子節點深度合併往上丟繼續計算，直到dfs
完。
java code:
-----------------------------------------------
class Solution {
int res = 0;
public int countPairs(TreeNode root, int distance) {
dfs(root, 1, distance);
return res;
}
List<Integer> dfs(TreeNode root, int h, int distance) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
if (root.left == null && root.right == null) {
list.add(h);
return list;
}
List<Integer> left = dfs(root.left, h + 1, distance);
List<Integer> right = dfs(root.right, h + 1, distance);
// 計算
for (int h1 : left) {
for (int h2 : right) {
if ((h1 - h) + (h2 - h) <= distance) {
res++;
}
}
}
list.addAll(left);
list.addAll(right);
return list;
}
}
-----------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://ptt-website.tw/Marginalman/M.1721298452.A.783