Python recursive solution with explanation


  • 0
    J

    When ask the best value of one node, we should know 7 things.

    1. its own value;
    2. its left child's value;
    3. its right child's value
    4. its left child's left child's value;
    5. its left child's right child's value;
    6. its right child's left child's value;
    7. its right child's right child's value
      the best value of current node is either: 1 + 4 + 5 + 6 + 7 or 2 + 3
      What we need to do is to compare them and return current node's best value and its left child's value and its right child's value to its parent because its parent need those information.
    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            self.max = 0
            self.rob_tree(root)
            return self.max
    
        def rob_tree(self, node):
            if not node:
                return 0, 0, 0
            l_son, l_grandson_l, l_grandson_r = self.rob_tree(node.left)
            r_son, r_grandson_l, r_grandson_r = self.rob_tree(node.right)
            cur_max = max(node.val + l_grandson_l + l_grandson_r + r_grandson_l +
                          r_grandson_r, l_son + r_son)
            if cur_max > self.max:
                self.max = cur_max
            return cur_max, l_son, r_son
    

Log in to reply
 

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