# LeetCode: 337. 打家劫舍 III¶

## 1、题目描述¶

     3
/ \
2   3
\   \
3   1


     3
/ \
4   5
/ \   \
1   3   1


## 2、解题思路¶

​ 使用深度优先搜索，我们针对每一层，都需要这样判断

• 偷当前层，那么就是当前层的值，加上左子树的

​ 下面的这个超时了，换个方式重新写

class Solution:
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""

if not root:
return 0

sum0 = root.val

sum1 = self.rob(root.left) + self.rob(root.right)

if root.left:
sum0 += self.rob(root.left.left) + self.rob(root.left.right)

if root.right:
sum0 += self.rob(root.right.left) + self.rob(root.right.right)

return max(sum0, sum1)


​ 嘿嘿嘿，使用大招，用C写一遍

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
int rob(struct TreeNode* root) {
if (root == NULL) {
return 0;
}

int sum0 = root->val;

int sum1 = 0;

sum1 += rob(root->left) + rob(root->right);

if (root->left != NULL) {
sum0 += rob(root->left->left) + rob(root->left->right);
}

if (root->right != NULL) {
sum0 += rob(root->right->left) + rob(root->right->right);
}

return sum0 > sum1 ? sum0 : sum1;
}


​ 通过了，不过耗费时间太长了，学习一下别人的思路

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/

int dfs(struct TreeNode *root, int *l, int *r) {
if (!root) {
return 0;

}
int ll = 0;
int lr = 0;
int rl = 0;
int rr = 0;

*l = dfs(root->left, &ll, &lr);
*r = dfs(root->right, &rl, &rr);

int sum0 = root->val + ll + lr + rl + rr;
int sum1 = *l + *r;

return sum0 > sum1 ? sum0 : sum1;
}
int rob(struct TreeNode *root) {
if (!root) {
return 0;
}
int l = 0;
int r = 0;
return dfs(root, &l, &r);

}


​ 思路差不多，分析一下区别在哪里，主要是减少了判断的情况