leetcode-bt

337. House Robber III.py

# 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:
    """
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative?
            any negative val inside the tree?
    Thought Process
        For each node, we need to get maximum profit if we rob current node and we don't rob current node. 
        
        If I rob current node(in the same level), I cannot rob his children.
        If I don't rub current node(in the same level), I can rob all children in the next node.
            
            rob = r.val + l_not + r_not
            not_rob = max(l_rob+r_rob,l_rob+r_not,l_not+r_rob,l_not+r_not) # all possible combinations
            
        
        return max(rob, not_rob) in the root
    During dfs, for each node, return max profix I can get if I rob and I don't rob.
    
              3
             / 
            4
           / \
          3   2   --> 3+3+2
    Ref:
        https://www.youtube.com/watch?v=HllsaLY2Fy8&ab_channel=ThinkFWD
    """
    def rob(self, root: TreeNode) -> int:
        """
        T:O(n)
        S:O(h)
        """
        if not root:
            return 0
        
        def dfs(r):
            if not r:
                return 0, 0
            l_rob, l_not=dfs(r.left)
            r_rob, r_not=dfs(r.right)
            rob = r.val + l_not + r_not
            not_rob = max(l_rob+r_rob,l_rob+r_not,l_not+r_rob,l_not+r_not)
            return rob, not_rob
        rob, not_rob = dfs(root)
        return max(rob, not_rob)