Leetcode 337. 打家劫舍 III（DAY 88) ---- Leetcode Hot 100
本文共 1223 字，大约阅读时间需要 4 分钟。
原题题目
代码实现
在这里，我将详细解释并优化给定的二叉树劫持问题的代码实现。
二叉树劫持问题要求我们选择一个子树，使得该子树的根节点值加上其左右子树的劫持值之和最大。通过递归方法，我们可以有效地计算每个节点的劫持值，并选择最优解。
以下是优化后的代码：
#include using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};unordered_map m;int rob(TreeNode* root) { if (!root) return 0; int l = rob(root->left); int r = rob(root->right); int ll = 0, lr = 0, rl = 0, rr = 0; if (root->left) { ll = m[root->left->left] ? m[root->left->left->val] : 0; lr = m[root->left->right] ? m[root->left->right->val] : 0; } if (root->right) { rl = m[root->right->left] ? m[root->right->left->val] : 0; rr = m[root->right->right] ? m[root->right->right->val] : 0; } int current = ll + lr + rl + rr + root->val; int total = l + r; if (total >= current) { m[root] = total; } else { m[root] = current; } return m[root];}
代码解释
结构定义：定义了一个二叉树的节点结构，包含值、左指针和右指针。 字典初始化：使用字典m来存储每个节点及其对应的劫持值。 递归函数：rob函数处理给定的根节点，返回其劫持值。 递归调用：分别递归处理根节点的左孩子和右孩子，获取左右子树的劫持值。 子树劫持值计算：根据子树是否存在，获取其左右子树的劫持值。 比较与赋值：计算当前节点及其子树的总劫持值，决定是否保留当前节点，更新字典m。 返回结果：返回当前节点的劫持值。 通过这种方法，我们可以有效地计算二叉树的劫持值，并选择最优的子树。
转载地址：http://fcni.baihongyu.com/