Clear 8-line DP Python with comments


  • 0

    The recurrence relation: dp[i] = max(root.val + dp[i -2], dp[i - 1]). Then, apply it to a tree.

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(root):
                if not root:
                    return (0, 0) # (_pre, _ppre), _pre->dp[i - 1], _ppre->dp[i - 2]
                leftpre, leftppre = dfs(root.left)
                rightpre, rightppre = dfs(root.right)
                ppre = leftpre + rightpre
                pre = max(root.val + leftppre + rightppre, ppre) 
                return pre, ppre
            return dfs(root)[0]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.