一个二叉树，每个节点有一个正整数数值。存在某个节点子集，使得其中节点对应的数值的和最大，前提：如果某节点在此子集中，其直接父亲节点和直接儿子节点不得出现在此子集中。求这个最大值。
动态规划。
最大值一定是在下面两种情况之一：根节点在子集中，但根节点的直接儿子节点不在子集中；根节点不在子集中。即最大值要么是根节点的所有孙子节点（儿子节点的儿子节点，最多4个）的最大值之和加上根节点的值，要么是两个儿子节点的最大值之和。显然计算子树最大值的方法是可以递归的，递归的终结状态是空树（最大值为0）。
请注意，上述方法中，某个节点为根节点的子树的最大值要求多次，所以要使用填表法来避免重复运算。
- 空间复杂度：O(n) n为节点个数
- 时间复杂度：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 {
private:
map<TreeNode*, int> table;
public:
int rob(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (table.find(root) != table.end()) {
return table[root];
}
int a = root->val;
if (root->left != NULL) {
a += rob(root->left->left);
a += rob(root->left->right);
}
if (root->right != NULL) {
a += rob(root->right->left);
a += rob(root->right->right);
}
int b = rob(root->left) + rob(root->right);
int max = (a > b) ? a : b;
table.insert(pair<TreeNode*, int> (root, max));
return max;
}
};
