[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)，常数空间，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int rob(TreeNode* root) {
	auto res = robHelper(root);
	return max(res.first, res.second);
	}
	private:
	//pair.first represent max value when we select current node, pair.second represent max value when we does not select current node
	pair<int, int> robHelper(TreeNode* root)
	{
	if(!root)return {0, 0};
	auto left = robHelper(root->left);
	auto right = robHelper(root->right);
	return {left.second + right.second + root->val, max(left.first, left.second) + max(right.first, right.second)};
	}
	};

view raw House Robber III.cpp hosted with ❤ by GitHub

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