leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历-蒲公英云

leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

这道题意很简单，就是父亲节点和自己不可以同时抢劫，这里设置一个返回数字res，其中res[0]表示抢劫当前节点， res[1]不抢劫当前节点，直接DFS递归遍历即可实现。

建议和这道题leetcode 740. Delete and Earn 动态规划DP、leetcode 198. House Robber 入室抢劫 + DP求解和这道题 leetcode 213. House Robber II 入室抢劫抢劫问题一起学习。

代码如下：

/*class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}*/
/*
 * 这其实也是DP的解决方法之一，
 * */
class Solution
{
    public int rob(TreeNode root)
    {
        if(root==null)
            return 0;
        int []res=getRes(root);
        return Math.max(res[0], res[1]);
    }
    /*
     * res[0]表示抢劫当前节点的记录的最大值
     * res[1]表示不抢劫当前的结点的记录的最大值
     * */
    public int[] getRes(TreeNode root) 
    {
        int[] res=new int[2];
        if(root==null)
            return res;
        else 
        {
            int[] left=getRes(root.left);
            int[] right=getRes(root.right);
            //抢劫当前节点，然后不抢劫其子节点
            res[0]=root.val + left[1] + right[1];
            //不抢劫当前节点，然后可以抢劫或者不抢劫其子节点
            res[1]=Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            return res;
        }
    }
}

下面是C++的做法，和上面的思路一模一样

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
/*
struct TreeNode 
{
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution 
{
public:
    int rob(TreeNode* root)
    {
        vector<int> res = dfs(root);
        return max(res[0], res[1]);
    }
    vector<int> dfs(TreeNode* root)
    {
        vector<int> res(2, 0);
        if (root == NULL)
            return res;
        else
        {
            vector<int> left = dfs(root->left);
            vector<int> right = dfs(root->right);
            res[0] = root->val + left[1] + right[1];
            res[1] = max(left[0], left[1]) + max(right[0], right[1]);
            return res;
        }
    }
};