leetcode 337. House Robber III

用动态规划的思想解决这道题。

对于每一个节点，只有两种可能，偷或者不偷。

对于一颗以root为根节点的二叉树，定义rob表示偷root节点能从这棵二叉树偷到的最大金额。定义notrob表示不偷root节点能从这棵二叉树偷到的最大金额。

递推公式分析如下：

rob = root->val + （不偷左孩子能从左子树偷到的最大金额）+（不偷右孩子能从右子树偷到的最大金额）

notrob = （从左子树能偷到的最大金额）+（从右子树能偷到的最大金额）

求root的值，需要先求左子树和右子树的情况，因此需要用二叉树的后序遍历，先递归的处理左子树和右子树。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        int rob_root;   //偷根节点能偷到的最大金额
        int notrob_root;//不偷根节点能偷到的最大金额
        postRob(root,rob_root,notrob_root);
        return max(rob_root,notrob_root);
    }

    void postRob(TreeNode* root,int &rob,int &notrob){
        if(root == nullptr)
        {
            rob = 0;
            notrob = 0;
            return;
        }
        int leftrob=0;   //偷左孩子能从左子树偷到的最大金额
        int leftnotrob=0;//不偷左孩子能从左子树偷到的最大金额
        postRob(root->left,leftrob,leftnotrob);
        int rightrob=0;   //偷右孩子能从右子树偷到的最大金额
        int rightnotrob=0;//不偷右孩子能从右子树偷到的最大金额
        postRob(root->right,rightrob,rightnotrob);
        rob = root->val + leftnotrob + rightnotrob;
        notrob = max(leftrob,leftnotrob) + max(rightrob,rightnotrob);
    }
};