题目大意：给你一棵二叉树，不能同时取两个相邻的节点(parent/child)，问最多能取得的节点的值的和是多少。
Problem:
https://leetcode.com/problems/house-robber-iii/description/
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.
Idea:
Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)
Solution 1: Recursion w/o memorization
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 1289 ms class Solution { public: int rob(TreeNode* root) { if (root == nullptr) return 0; int val = root->val; int ll = root->left ? rob(root->left->left) : 0; int lr = root->left ? rob(root->left->right) : 0; int rl = root->right ? rob(root->right->left) : 0; int rr = root->right ? rob(root->right->right) : 0; return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right)); } }; |
Solution 2: Recursion w/ memorization
Time complexity: O(n)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 15 ms class Solution { public: int rob(TreeNode* root) { if (root == nullptr) return 0; if (m_.count(root)) return m_[root]; int val = root->val; int ll = root->left ? rob(root->left->left) : 0; int lr = root->left ? rob(root->left->right) : 0; int rl = root->right ? rob(root->right->left) : 0; int rr = root->right ? rob(root->right->right) : 0; return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right)); } private: unordered_map<TreeNode*, int> m_; }; |
Solution 3: Recursion return children’s value
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 10 ms (beats 97.57%) class Solution { public: int rob(TreeNode* root) { int l = 0; int r = 0; return rob(root, l, r); } private: // return rob(root) and stores rob(root->left/right) in l/r. int rob(TreeNode* root, int& l, int& r) { if (root == nullptr) return 0; int ll = 0; int lr = 0; int rl = 0; int rr = 0; l = rob(root->left, ll, lr); r = rob(root->right, rl, rr); return max(root->val + ll + lr + rl + rr, l + r); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
""" Author: Huahua Running time: 64 ms (beats 93.18%) """ class Solution: def rob(self, root): def rob(root): if not root: return 0, 0, 0 l, ll, lr = rob(root.left) r, rl, rr = rob(root.right) return max(root.val + ll + lr + rl + rr, l + r), l, r return rob(root)[0] |
Related Problems: