213.Hiccup III

2024-01-01

字数统计: 158字 | 阅读时长: 1min

topic：

screenshot2023-09-18 afternoon1.08.41.png
topic链接

Thought：

Reference ylb 大佬的answer，
这道题andHiccup1and2The difference is，这道题是一棵Binary tree，And you can’t rob the neighboring node。
So his youngest child problem is：Robbing the current node，You can’t rob your left and right children。
If you steal root node，那么不能偷取其左右子node，Result root.val+lb +rb；
If not steal root node，那么可以偷取其左右子node，Result max(la, lb)+max(ra ,rb)。

Code：

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def _rob(root: Optional[TreeNode]) -> (int, int):
            # Minority problem:dp[i]=dp[i-2]+nums[i], dp[i-1]
            if not root:
                return 0, 0
            la, lb = _rob(root.left)
            ra, rb = _rob(root.right)
            return root.val + lb + rb, max(la, lb) + max(ra, rb)
        return max(_rob(root))