[LeetCode]House Robber III

树形DP的问题。我们用localMax[i][0]表示以i为root的子树，在偷house i的时候可以偷到的最大值；localMax[i][1]表示以i为root的子树，在不偷偷house i的时候可以偷到的最大值那么。我们有递推公式：

• localMax[i][0] = max(localMax[i->left][0], localMax[i->left][1]) + max(localMax[i->right][0], localMax[i->right][1])
• localMax[i][1] = localMax[i->left] + localMax[i->right] + house[i]

因为树已经建好了我们直接递归return一个pair，pair first代表localMax[i][1], pair second代表localMax[i][0]。时间复杂度O(n)，常数空间，代码如下：

如果对树形DP感兴趣，想知道如何用array对输入数据建树并且DP的，可以参考这篇文章。