# 337.打家劫舍III

## 问题描述
[337.打家劫舍III](https://leetcode.cn/problems/house-robber-iii/)

## 解题思路
严格来说，这一题和[198.打家劫舍](https://leetcode.cn/problems/house-robber/)，[213.打家劫舍II](https://leetcode.cn/problems/house-robber-ii/)的思路并不一致。

首先，这一道题遍历的是树，而不是一个数组。要比较的是选择目前节点和目前节点左子节点+右子节点，因此在遍历方式上需要采取**后序遍历**。

同时，作为二叉树的问题，一般是考虑递归进行处理：
- 递归的终止条件：
    - 当前节点为空；
- 递归函数的返回值：
    - 返回一个长度为2的数组`dp`，`dp[0]`表示不偷当前节点的最大金钱，`dp[1]`表示偷当前节点的最大金钱；
- 本级递归做什么：
    - 计算偷当前节点的收益`val1`，不偷当前节点的收益`val2`，返回`{val2, val1}`。

## 代码
```cpp
class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};
```