youngyangyang04/leetcode-master-comment

[Vssue]0337.打家劫舍III.md

youngyangyang04 opened this issue · 3 comments

Du1in9 commented 
private int[] robTree(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = robTree(node.left);
    int[] right = robTree(node.right);
    int no = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    int yes = node.val + left[0] + right[0];
    return new int[]{no, yes};
}
// 例: root = [3,4,5,1,3,null,1], 从下往上看:
robTree(3): left = robTree(4) = [4,4], right = robTree(5) = [1,5]
    yes = 3+4+1 = 8 (偷), no = 4+5 = 9 (不偷), 返回 [9,8]
robTree(4): left = robTree(1) = [0,1], right = robTree(3) = [0,3]
    yes = 4+0+0 = 4 (偷), no = 1+3 = 4 (不偷), 返回 [4,4]
robTree(5): left = robTree(null) = [0,0], right = robTree(1) = [0,1]
    yes = 5+0+0 = 5 (偷), no = 0+1 = 1 (不偷), 返回 [1,5]
robTree(1): left = robTree(null) = [0,0], right = robTree(null) = [0,0]
    yes = 1+0+0 = 1 (偷), no = 0+0 = 0 (不偷), 返回 [0,1]
robTree(3): left = robTree(null) = [0,0], right = robTree(null) = [0,0]
    yes = 3+0+0 = 1 (偷), no = 0+0 = 0 (不偷), 返回 [0,3]
robTree(1): left = robTree(null) = [0,0], right = robTree(null) = [0,0]
    yes = 1+0+0 = 1 (偷), no = 0+0 = 0 (不偷), 返回 [0,1]
  • 👍1
  • ❤️1