【Leetcode HOT100】打家劫舍 III c++

题目描述：

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

递归 c++代码：

/**
 * 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 solve(TreeNode* root){
        if(root==nullptr)return 0;
        int get_root = 0,no_root=0;
        get_root += root->val;
        if(root->left!=nullptr){
            get_root+=solve(root->left->left);
            get_root+=solve(root->left->right);
        }
        if(root->right!=nullptr){
            get_root+=solve(root->right->left);
            get_root+=solve(root->right->right);
        }
        no_root += solve(root->left)+solve(root->right);
        return max(get_root,no_root);
    }
    int rob(TreeNode* root) {
        return solve(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

下一步如何选取节点，取决于是否选择当前根节点。

若选择根节点root，则左子节点和右子节点都不可以选择，接下来应该选择左子节点的左右子节点，和右子节点的左右节点。

若不选择根节点root，则应该选择左子节点和右子节点。

每次递归应该返回较大的值：

return max(root->val+solve(root->left->left)+solve(root->left->right)+solve(root->right->left)+solve(root->right->right), solve(root->left)+solve(right))
1

递归过程中有重复计算，所以会超时。

记忆化递归（动态规划） c++代码：

/**
 * 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:
    map<TreeNode*,int> rec;
    int rob(TreeNode* root) {
        if(root==nullptr)return 0;
        if(rec[root]!=0)return rec[root];
        int s = root->val;
        if(root->left!=nullptr){
            s += rob(root->left->left);
            s += rob(root->left->right);
        }
        if(root->right!=nullptr){
            s += rob(root->right->left);
            s += rob(root->right->right);
        }
        int result = max(s,rob(root->left)+rob(root->right));
        rec[root]=result;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

每个root，都用map记录一下root对应的计算结果（选择偷当前节点或不偷的较大值）

总结：

二叉树用动态规划时，不适合用dp[]数组记录，适合用哈希表。