House Robber III
程序员文章站
2022-07-12 12:30:35
...
1. 解析
题目大意,求解二叉树所有非相邻节点和的最大值。题目还是很难的,就是会给人一种有思路,但就是写不出来的感觉,要求对递归理解非常透彻才有可能设计出来。
2. 分析
参考@Grandyang的解法,主要分成两种情况考虑:
①考虑根节点的值,不考虑左右子树的根节点
②不考虑根节点的值,考虑左右子树的根节点
综上,为了不重复的检索,我们可以借助hashtable存储检索过的节点,用带有记忆功能的递归,每一次递归返回①②情况的最大值即可。虽然思路看起来蛮简单的,但中间的递归过程还是蛮复杂的,有空我也要自己动手去探索一下过程~~~
/**
* 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) {
map<TreeNode*, int> exist;
return DFS(root, exist);
}
int DFS(TreeNode* root, map<TreeNode*, int>& exist){
if (!root) return 0;
if (exist[root]) return exist[root];
int val = 0;
if (root->left){ //只包含
val += DFS(root->left->left, exist) + DFS(root->left->right, exist);
}
if (root->right){
val += DFS(root->right->left, exist) + DFS(root->right->right, exist);
}
val = max(DFS(root->left, exist) + DFS(root->right, exist), root->val + val);
exist[root] = val;
return val;
}
};
第二种解法思路差不多,将上面的两个过程值保存在vector数组当中,即res[0]代表上面的第①种情况,res[1]代表第②种情况。
/**
* 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){
vector<int> res = DFS(root);
return max(res[0], res[1]);
}
vector<int> DFS(TreeNode* root){
if (! root) return vector<int>(2, 0);
vector<int> left = DFS(root->left);
vector<int> right = DFS(root->right);
vector<int> res(2, 0);
res[0] = max(left[0], left[1]) + max(right[0], right[1]);
res[1] = root->val + left[0] + right[0];
return res;
}
};
3. 类似的题目
Convert Sorted List to Binary Search Tree
推荐阅读
-
【LeeCode 简单 字符串 python3】557 反转字符串中的单词 III
-
【I·M·U_Ops】------III------ IMU自动化运维平台之CMDB(admin)
-
清凉光污染:酷冷至尊毁灭者III至尊版机箱体验
-
全球唯一4K/120Hz旗舰!索尼Xperia 1 III今晚开售:8499元起
-
Can you answer these queries III
-
惠普暗影精灵3游戏性能如何?惠普暗影精灵III代游戏本游戏体验评测详解
-
DDR III插槽信号定义图
-
Green House大号USB风扇
-
首款4K 120Hz旗舰!索尼Xperia 1 III海外价格偷跑:8592元
-
Green House发布新款时尚系列入耳耳机