邵阳市网站建设_网站建设公司_前端工程师_seo优化

目录

1.二叉树中的最大路径

a.核心思想

b.思路

c.步骤

2.C++的类型转换

1.二叉树中的最大路径

124. 二叉树中的最大路径和 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */ class Solution { public: int max_sum; // 全局变量，记录最大路径和 int dfs(TreeNode* node) { if (node == nullptr) return 0; // 递归计算左右子树的最大贡献值，如果为负则取0 int left_gain = std::max(dfs(node->left), 0); int right_gain = std::max(dfs(node->right), 0); // 计算以当前节点为根的路径和 int price_newpath = node->val + left_gain + right_gain; // 更新最大路径和 max_sum = std::max(max_sum, price_newpath); // 返回当前节点的值加上左右子树中较大的贡献值 return node->val + std::max(left_gain, right_gain); } int maxPathSum(TreeNode* root) { max_sum = INT_MIN; dfs(root); return max_sum; } };

a.核心思想

利用深度优先搜索（DFS）遍历二叉树，在遍历过程中维护当前路径的节点值之和以及当前路径的最大值。由于路径可以从任意节点开始和结束，因此在递归到每个节点时，需要考虑以该节点为路径的一部分的情况，同时更新最大路径和。

b.思路

① 使用后序遍历（左右根）的方式遍历二叉树，这样可以先处理子节点，再处理父节点。

② 在递归过程中，维护一个全局变量max_sum来记录当前找到的最大路径和。

③ 对于每个节点，计算其左右子树的最大贡献值（如果贡献值为负则取0，因为负贡献会减小路径和），然后将当前节点的值与左右子树的贡献值相加，得到以当前节点为根的路径和。

④ 更新max_sum，然后返回当前节点的值加上左右子树中较大的贡献值（因为路径只能选择一条分支继续向上延伸）。

c.步骤

① 定义一个全局变量max_sum初始化为一个很小的值（例如INT_MIN）。

② 编写递归函数dfs，参数为当前节点node。

③ 在dfs函数中：

• 如果节点为空，返回0。

• 递归计算左右子树的最大贡献值left_gain和right_gain。

• 计算以当前节点为根的路径和price_newpath。

• 更新max_sum。

• 返回当前节点的值加上左右子树中较大的贡献值。

④ 调用dfs函数从根节点开始遍历。

⑤ 返回max_sum。

2.C++的类型转换

C++类型转换分为显式类型转换和隐式类型转换，显式转换推荐使用四种类型转换操作符：

1. static_cast

   1. 用于基本类型转换（如int转double）、有继承关系的指针/引用向上转型（安全）或向下转型（需确保类型正确）。

   2. 示例：double d = static_cast<double>(5);

2. dynamic_cast

   1. 用于有继承关系的指针/引用向下转型，运行时检查类型安全。指针转换失败返回nullptr，引用转换失败抛出std::bad_cast异常。

   2. 示例：Derived* d = dynamic_cast<Derived*>(basePtr);

3. const_cast

   1. 仅用于添加/移除const属性（如const int*转int*），不可修改原始const对象。

   2. 示例：int* p = const_cast<int*>(&constVar);

4. reinterpret_cast

   1. 用于底层二进制重新解释（如指针转整数、结构体指针互转），高度危险，依赖平台实现。

   2. 示例：int i = *reinterpret_cast<int*>(ptr);

C风格转换（如(int)3.14）隐式且不安全，C++推荐优先使用上述操作符明确转换意图。隐式类型转换由编译器自动完成（如double赋值给int会截断小数），需注意精度损失或溢出风险。

希望这些内容对大家有所帮助！

感谢大家的三连支持！