house_robber_iii
1from utils import TreeNode 2from typing import Optional 3 4 5# @leet start 6class Solution: 7 def rob(self, root: Optional[TreeNode]) -> int: 8 """ 9 This question asks us to solve a problem where we traverse a binary tree, 10 and have to maximize our payoff given we can only take a parent or child 11 node at every time. 12 So, if we take our current node, we cannot take the left or right subtree's 13 payoff as well. 14 Thus, for each node, we want to be able to state the payoff for taking 15 it (its node.val + skipping its next level) or skipping the current node, 16 (taking the maximum of either skipping or taking its left and right child). 17 18 To do this, we have each node return its max payoff if we take this 19 node or if we don't take this node, and apply it to the starting node. 20 This is done by returning a tuple, of (rob, skip) for each node. For 21 each node, we either have the choice of robbing (where we take the node) 22 or skipping. We return that for each node. Then, at the end, we start 23 from the root and get the maximum result from that traversal. 24 """ 25 26 def dp(node): 27 if not node: 28 return (0, 0) 29 left = dp(node.left) 30 right = dp(node.right) 31 rob = node.val + left[1] + right[1] 32 skip = max(left) + max(right) 33 return (rob, skip) 34 35 return max(dp(root)) 36 37 38# @leet end 39 40 41def test(): 42 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def rob(self, root: Optional[TreeNode]) -> int: 9 """ 10 This question asks us to solve a problem where we traverse a binary tree, 11 and have to maximize our payoff given we can only take a parent or child 12 node at every time. 13 So, if we take our current node, we cannot take the left or right subtree's 14 payoff as well. 15 Thus, for each node, we want to be able to state the payoff for taking 16 it (its node.val + skipping its next level) or skipping the current node, 17 (taking the maximum of either skipping or taking its left and right child). 18 19 To do this, we have each node return its max payoff if we take this 20 node or if we don't take this node, and apply it to the starting node. 21 This is done by returning a tuple, of (rob, skip) for each node. For 22 each node, we either have the choice of robbing (where we take the node) 23 or skipping. We return that for each node. Then, at the end, we start 24 from the root and get the maximum result from that traversal. 25 """ 26 27 def dp(node): 28 if not node: 29 return (0, 0) 30 left = dp(node.left) 31 right = dp(node.right) 32 rob = node.val + left[1] + right[1] 33 skip = max(left) + max(right) 34 return (rob, skip) 35 36 return max(dp(root))
8 def rob(self, root: Optional[TreeNode]) -> int: 9 """ 10 This question asks us to solve a problem where we traverse a binary tree, 11 and have to maximize our payoff given we can only take a parent or child 12 node at every time. 13 So, if we take our current node, we cannot take the left or right subtree's 14 payoff as well. 15 Thus, for each node, we want to be able to state the payoff for taking 16 it (its node.val + skipping its next level) or skipping the current node, 17 (taking the maximum of either skipping or taking its left and right child). 18 19 To do this, we have each node return its max payoff if we take this 20 node or if we don't take this node, and apply it to the starting node. 21 This is done by returning a tuple, of (rob, skip) for each node. For 22 each node, we either have the choice of robbing (where we take the node) 23 or skipping. We return that for each node. Then, at the end, we start 24 from the root and get the maximum result from that traversal. 25 """ 26 27 def dp(node): 28 if not node: 29 return (0, 0) 30 left = dp(node.left) 31 right = dp(node.right) 32 rob = node.val + left[1] + right[1] 33 skip = max(left) + max(right) 34 return (rob, skip) 35 36 return max(dp(root))
This question asks us to solve a problem where we traverse a binary tree, and have to maximize our payoff given we can only take a parent or child node at every time. So, if we take our current node, we cannot take the left or right subtree's payoff as well. Thus, for each node, we want to be able to state the payoff for taking it (its node.val + skipping its next level) or skipping the current node, (taking the maximum of either skipping or taking its left and right child).
To do this, we have each node return its max payoff if we take this node or if we don't take this node, and apply it to the starting node. This is done by returning a tuple, of (rob, skip) for each node. For each node, we either have the choice of robbing (where we take the node) or skipping. We return that for each node. Then, at the end, we start from the root and get the maximum result from that traversal.
def
test():