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

[youngyangyang04]

https://www.programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html

[Du1in9]

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]