When ask the best value of one node, we should know 7 things.
- its own value;
- its left child's value;
- its right child's value
- its left child's left child's value;
- its left child's right child's value;
- its right child's left child's value;
- 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