借鉴DP思想: HouseRobberIII

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:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

题目大意

给定一二叉树，树节点上有权值，从树中选取一些不直接相邻的节点，使得节点和最大

思考过程

1. 简单粗暴，搜索完事，一个节点不外乎两种情况，选择 or 不选择；另外当前节点选择之后，子节点不能被选择；当前节点若不选择，则又可以分为四种情况

* 左选择，右不选

* 右选，左不选

* 左右都选

* 左右都不选

2. 写代码，好的然而超时（当然-_-后来看了其他的解答，才发现too young）

3. 因为看到有重复计算，于是朝动态规划考虑，于是想出这么个状态

d[0][1]，其中0表示存储遍历到当前节点时，取当前节点能达到的最大值，而1则表示，不取当前节点能达到的最大值

又因为是树节点，所以直接哈希表存储d[TreeNode*][]

4. 遍历顺序呢，习惯性后序遍历

5. 计算规则

// 显然，当前节点取了，子节点不能取

d[TreeNode*][0] = TreeNodeVal + d[LeftChild][1] + d[RightChild][1]

// 四种情况

d[TreeNode*][1] = max(d[LeftChild][0] + d[RightChild][0], d[LeftChild][1] + d[RightChild][0], d[LeftChild][0] + d[RightChild][1], d[LeftChild][1] + d[RightChild][1])

6. 总算过了，附代码；看了讨论的思路之后，觉得真是too young，╮(╯▽╰)╭

 class Solution {

 public:

     int rob(TreeNode* root) {

         if (root == NULL) {

             return ;

         }

         postOrder(root);

         return max(d[root][], d[root][]);

     }

     void postOrder(TreeNode* itr) {

         if (itr == NULL) {

             return;

         }

         postOrder(itr->left);

         postOrder(itr->right);

         auto dItr = d.insert(pair<TreeNode*, vector<int>>(itr, vector<int>(, )));

         auto leftItr = dItr.first->first->left;

         auto rightItr = dItr.first->first->right;

         int rL = dItr.first->first->left != NULL ? d[dItr.first->first->left][] : ;

         int rR = dItr.first->first->right != NULL ? d[dItr.first->first->right][] : ;

         int uL = dItr.first->first->left != NULL ? d[dItr.first->first->left][] : ;

         int uR = dItr.first->first->right != NULL ? d[dItr.first->first->right][] : ;

         dItr.first->second[] = dItr.first->first->val + uL + uR;

         dItr.first->second[] = max(max(max(rL + uR, uL + rR), rL + rR), uL + uR);

     }

 private:

     unordered_map<TreeNode*, vector<int>> d;

 };

巴特西

借鉴DP思想: HouseRobberIII

题目大意

思考过程

最新文章

热门文章