Re: [閒聊] 每日leetcode

看板Marginalman作者 (JerryChung)時間1年前 (2024/10/23 15:42), 1年前編輯推噓2(2推 0噓 11→)
留言13則, 3人參與, 1年前最新討論串1029/1548 (看更多)
https://leetcode.com/problems/cousins-in-binary-tree-ii 2641. Cousins in Binary Tree II 昨天的解完後看Similar Questions看到這題 今天就出了 打算用跟昨天一樣的解法 但後面測資錯了 有大師能幫看是哪邊有問題嗎 (( 用層數與父值當key 同父的就相加 之後把同一層key != parent的加起來 測資17的output第15層錯了 特調後測資18的12跟14層錯了 後面大概也都過不了 # 修改後的Code在最底下 Python Code: class Solution: def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[ TreeNode]: def c(node: TreeNode, res: defaultdict, level: int, parent: int): res[level][parent] += node.val if node.left: c(node.left, res, level+1, node.val) if node.right: c(node.right, res, level+1, node.val) def u(node: TreeNode, res: defaultdict, level: int, parent: int): if node.left: u(node.left, res, level+1, node.val) if node.right: u(node.right, res, level+1, node.val) node.val = sum(v for k, v in res[level].items() if k != parent) res = defaultdict(lambda: defaultdict(int)) c(root, res, 1, 0) # print(json.dumps({k: dict(v) for k, v in res.items()})) u(root, res, 1, 0) return root 哀 窩好爛 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.79.252 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729669365.A.7DC.html
→
10/23 15:52, 1年前 , 1F
如果同lv有好幾個一樣的parent怎麼辦
10/23 15:52, 1F
推
10/23 15:52, 1年前 , 2F
直接用node當parent 不要用node.val 值可能重複?
10/23 15:52, 2F
→
10/23 15:52, 1年前 , 3F
應該是只能跳過一個
10/23 15:52, 3F
→
10/23 15:52, 1年前 , 4F
我是全部sum up再減掉自己這個
10/23 15:52, 4F
→
10/23 15:58, 1年前 , 5F
那值不重複的Tree是什麼 我以為固定不重複 ((
10/23 15:58, 5F
→
10/23 16:02, 1年前 , 6F
他只有說binary treeㄚ
10/23 16:02, 6F
→
10/23 16:03, 1年前 , 7F
parent的node.val改為node之後過了 但測資38 TLE ((
10/23 16:03, 7F
→
10/23 16:07, 1年前 , 8F
跟binary tree不熟 :(
10/23 16:07, 8F
推
10/23 16:15, 1年前 , 9F
1e5平衡樹，最後一層node太多ㄌ 1e5 / 2
10/23 16:15, 9F
→
10/23 16:15, 1年前 , 10F
每次sum都迴圈會變n^2
10/23 16:15, 10F
→
10/23 16:18, 1年前 , 11F
改多放一個 res[level]['total']
10/23 16:18, 11F
→
10/23 16:18, 1年前 , 12F
sum 改成 'total' - parent 過了 開心 :)
10/23 16:18, 12F
Python Code: # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[ TreeNode]: def c(node: TreeNode, res: defaultdict, level: int, parent: int): res[level]['total'] += node.val res[level][parent] += node.val if node.left: c(node.left, res, level+1, node) if node.right: c(node.right, res, level+1, node) def u(node: TreeNode, res: defaultdict, level: int, parent: int): if node.left: u(node.left, res, level+1, node) if node.right: u(node.right, res, level+1, node) node.val = res[level]['total'] - res[level][parent] res = defaultdict(lambda: defaultdict(int)) c(root, res, 1, 0) u(root, res, 1, 0) return root ※ 編輯: JerryChungYC (220.129.79.252 臺灣), 10/23/2024 16:19:51
→
10/23 16:21, 1年前 , 13F
謝謝兩位大師捏 <3
10/23 16:21, 13F
‣ 更多 JerryChungYC 的文章
文章代碼(AID): #1d6AZrVS (Marginalman)
討論串 (同標題文章)
完整討論串 (本文為第 1029 之 1548 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共1548篇)
‣ 更多 JerryChungYC 的文章
文章代碼(AID): #1d6AZrVS (Marginalman)