算法

每日leetcode-337

  1. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

1
2
3
4
5
  3
 / \
2   3
 \   \ 
  3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

1
2
3
4
5
     3
   / \
  4   5
 / \   \ 
1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解答

使用后序遍历非递归，分别记录每一个节点的抢劫能抢到的钱，以及不抢它能抢到的钱，总之还是动态规划。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 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 {
public:
    int rob(TreeNode* root) {
        if (!root) {
            return 0;
        }
        unordered_map<TreeNode*, int> data;  // 抢了这个节点的话，可以有多少钱
        unordered_map<TreeNode*, int> pre;  // 不抢这个节点的话，可以有多少钱
        // 后序遍历，先把孩子整完了，在整爹，具体看http://www.bilibili.com/video/av23885544/
        // 每一次后序遍历的时候，先把指针p指向左子树，再对根节点做个标记后指向右子树
        TreeNode* p = root;
        stack<TreeNode*> tree;
        stack<bool> check;
        while (p || !tree.empty()) {
            if (p) {
                tree.push(p);
                check.push(false);
                p = p->left;
            }
            else {
                bool need_pop = check.top();
                if (need_pop) {
                    TreeNode* check_node = tree.top();
                    check.pop();
                    tree.pop();
                    int check_val = check_node->val;;
                    int pre_val = 0;
                    if (check_node->left) {
                        check_val += pre[check_node->left];
                        pre_val += data[check_node->left];
                    }
                    if (check_node->right) {
                        check_val += pre[check_node->right];
                        pre_val += data[check_node->right];
                    }
                    data[check_node] = max(check_val, pre_val);
                    pre[check_node] = pre_val;
                }
                else {
                    check.pop();
                    check.push(true);
                    p = tree.top()->right;
                }
            }
        }
        return data[root];
    }
};

http://www.bilibili.com/video/av23885544/ 这里的后序遍历非递归的说明挺清楚的

后序遍历递归版本

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
33
34
35
36
37
38
39
/**
 * 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 {
public:
    int rob(TreeNode* root) {
        if (!root) {
            return 0;
        }
        unordered_map<TreeNode*, int> data;  // 抢了这个节点的话，可以有多少钱
        unordered_map<TreeNode*, int> pre;  // 不抢这个节点的话，可以有多少钱
        // 这次直接用递归方式的后序遍历
        search(root, data, pre);
        return data[root];
    }

    void search(TreeNode* check_node, unordered_map<TreeNode*, int>& data, unordered_map<TreeNode*, int>& pre) {
        int check_val = check_node->val;;
        int pre_val = 0;
        if (check_node->left) {
            search(check_node->left, data, pre);
            check_val += pre[check_node->left];
            pre_val += data[check_node->left];
        }
        if (check_node->right) {
            search(check_node->right, data, pre);
            check_val += pre[check_node->right];
            pre_val += data[check_node->right];
        }
        data[check_node] = max(check_val, pre_val);
        pre[check_node] = pre_val;
    }
};

其实比上面的要慢，主要是因为unordered_map的使用，其实并不需要用这个map，每一次返回两个数就行

优化

换成返回两个数

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
/**
 * 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 {
public:
    int rob(TreeNode* root) {
        if (!root) {
            return 0;
        }
        // 这次直接用递归方式的后序遍历
        auto ans = search(root);
        return ans.first;
    }

    pair<int, int> search(TreeNode* check_node) {
        if (!check_node) {
            return {0, 0};
        }
        auto left = search(check_node->left);
        auto right = search(check_node->right);
        int check_val = check_node->val + left.second + right.second;
        int pre_val = left.first + right.first;
        return {max(check_val, pre_val), pre_val};
    }
};