Re: [閒聊] 每日leetcode

[JerryChungYC (JerryChung)]

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
→ sixB: 如果同lv有好幾個一樣的parent怎麼辦
推 dont: 直接用node當parent 不要用node.val 值可能重複?
→ sixB: 應該是只能跳過一個
→ sixB: 我是全部sum up再減掉自己這個
→ JerryChungYC: 那值不重複的Tree是什麼 我以為固定不重複 ((
→ sixB: 他只有說binary treeㄚ
→ JerryChungYC: parent的node.val改為node之後過了 但測資38 TLE ((
→ JerryChungYC: 跟binary tree不熟 :(
推 sixB: 1e5平衡樹，最後一層node太多ㄌ 1e5 / 2
→ sixB: 每次sum都迴圈會變n^2
→ JerryChungYC: 改多放一個 res[level]['total']
→ JerryChungYC: sum 改成 'total' - parent 過了 開心 :)
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
→ JerryChungYC: 謝謝兩位大師捏 <3