20202026年 年中報解讀# 2025年， 2026年評價高評價自動快速門業(yè)力扣 LeetCode 337. 打家劫舍 III

• Definition for循環(huán)依賴

  Definition for each node, two cases: 1. rob it, then can't rob left and right; 2. not rob it, then can rob left and right

  遞歸的話不多說，直接遞歸，注意記憶化

  Definition for each node, return two values: [rob, not_rob]

  rob = root.val + left[1] + right[1]

  not_rob = max(left[0], left[1]) + max(right[0], right[1])

  so use post-order traversal, since need left and right first

class Solution: 遞歸 + 記憶化 class Solution:

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 rob(self, root: Optional[TreeNode]) -> int: def dfs(node):

return (rob, not_rob)

        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)
        #rob current node: current value + not rob left + not rob right
        rob = node.val + left[1] + right[1]
        #not rob current node: max of left(rob or not) + max of right(rob or not)
        not_rob = max(left[0], left[1]) + max(right[0], right[1])
        return (rob, not_rob)
    return max(dfs(root))

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 rob(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return (0,0) left_rob, left_not = dfs(node.left) right_rob, right_not = dfs(node.right) curr_rob = node.val + left_not + right_not curr_not = max(left_rob, left_not) + max(right_rob, right_not) return (curr_rob, curr_not) return max(dfs(root))

（免責聲明：本文為本網(wǎng)站出于傳播商業(yè)信息之目的進行轉(zhuǎn)載發(fā)布，不代表本網(wǎng)站的觀點及立場。本文所涉文、圖、音視頻等資料的一切權(quán)利和法律責任歸材料提供方所有和承擔。本網(wǎng)站對此資訊文字、圖片等所有信息的真實性不作任何保證或承諾，亦不構(gòu)成任何購買、投資等建議，據(jù)此操作者風險自擔。） 本文為轉(zhuǎn)載內(nèi)容，授權(quán)事宜請聯(lián)系原著作權(quán)人，如有侵權(quán)，請聯(lián)系本網(wǎng)進行刪除。