記錄了初步解題思路 以及本地實現代碼；并不一定為最優 也希望大家能一起探討 一起進步

---

2/26 938. 二叉搜索樹的范圍和

dfs 判斷節點值是否在區間內

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def rangeSumBST(root, low, high):""":type root: TreeNode:type low: int:type high: int:rtype: int"""def dfs(node):ret = 0if node.val>low:if node.left:ret = dfs(node.left)if node.val>=low and node.val<=high:ret+=node.valif node.val<high:if node.right:ret += dfs(node.right)return retreturn dfs(root)

---

2/27 2867. 統計樹中的合法路徑數目

歐拉篩篩選質數
以質數節點為根 深搜所有非質數的子樹
求字數大小 任意兩個不同子樹節點 路徑都通過質數根節點
只有一個節點為質數 符合題意

def countPaths(n, edges):""":type n: int:type edges: List[List[int]]:rtype: int"""prime=[]isprime = [True]*(n+1)isprime[1]=Falsefor i in range(2,n+1):if isprime[i]:prime.append(i)for p in prime:if p*i>n:breakisprime[p*i]=Falseif i%p==0:breakm=[[] for _ in range(n+1)]for i,j in edges:m[i].append(j)m[j].append(i)global seendef dfs(i,pre):global seenseen.append(i)for j in m[i]:if j!=pre and not isprime[j]:dfs(j,i)ans = 0cnt=[0]*(n+1)for i in range(1,n+1):if not isprime[i]:continuecur = 0for j in m[i]:if isprime[j]:continueif cnt[j]==0:seen = []dfs(j,0)for k in seen:cnt[k] = len(seen)ans+=cnt[j]*curcur+=cnt[j]ans+=curreturn ans

---

2/28 2673. 使二叉樹所有路徑值相等的最小代價

滿二叉樹有n個節點 那么存在(n+1)//2個葉子節點
對于兩個兄弟葉子節點 除了改變其自身 無法改變兩個節點路徑和的差值
所以將小的葉子節點增加到大的即可
改完葉子節點 將葉子節點的值增加到父節點中 依舊考慮父節點和叔節點的情況

def minIncrements(n, cost):""":type n: int:type cost: List[int]:rtype: int"""ans=0for i in range(n-2,0,-2):ans += abs(cost[i]-cost[i+1])cost[i//2] += max(cost[i],cost[i+1])return ans

---

2/29 2581. 統計可能的樹根數目

首先計算以0位根節點時猜對的個數cnt
當根節點從0換到其某個子節點x時
除了0,x的父子關系發生變化 其他沒有變化
所以如果此時(0,x)在猜測中 則cnt-1
如果(x,0)在猜測中 則cnt+1
遇到cnt>=k 則ans+1

def rootCount(edges, guesses, k):""":type edges: List[List[int]]:type guesses: List[List[int]]:type k: int:rtype: int"""g=[[] for _ in range(len(edges)+1)]for x,y in edges:g[x].append(y)g[y].append(x)s = {(x,y) for x,y in guesses}global cnt,ansans = 0cnt = 0def dfs(x,p):global cntfor y in g[x]:if y!=p:cnt += (x,y) in sdfs(y,x)dfs(0,-1)def reroot(x,p,cnt):global ansif cnt>=k:ans+=1for y in g[x]:if y!=p:reroot(y,x,cnt-((x,y) in s) +((y,x) in s))reroot(0,-1,cnt)return ans

---

3/1 2369. 檢查數組是否存在有效劃分

dp[i+1]判斷是否能夠有效劃分0~i

def validPartition(nums):""":type nums: List[int]:rtype: bool"""n=len(nums)dp=[False]*(n+1)dp[0]=Truefor i,x in enumerate(nums):if (i>0 and dp[i-1] and x==nums[i-1]) or (i>1 and dp[i-2] and (x==nums[i-1]==nums[i-2] or x==nums[i-1]+1==nums[i-2]+2)):dp[i+1]=Truereturn dp[n]

---

3/2 2368. 受限條件下可到達節點的數目

不考慮受限的節點 建圖
DFS搜索

def reachableNodes(n, edges, restricted):""":type n: int:type edges: List[List[int]]:type restricted: List[int]:rtype: int"""s = set(restricted)m = [[] for _ in range(n)]for x,y in edges:if x not in s and y not in s:m[x].append(y)m[y].append(x)def dfs(x,f):cnt = 1for y in m[x]:if y!=f:cnt += dfs(y,x)return cntreturn dfs(0,-1)

---

3/3

---