相对于第一次开始刷题的人来说我之前有过在校acm队训练的一段时间，所以之前刷的是Codeforces，现在为了进厂开始练习leetcode上的题目。
在开始做题之前首先肯定是给自己打一堆决心，然后我把这个账号之前发布的那些乱码七糟的小东西全部删掉，开始一个崭新账号的书写，所以不管自己最后会坚持到哪一步，不管自己以后会去做什么，至少证明我有过一段时间曾经将屠龙之技列在了我的行程上。
今天作题的时候听的歌是Waves-LAKEY INSPIRED
哦顺便介绍一下我用的编译器和语言，编译器是VS 语言是Cpp，cpp对于算法来说可以很清晰的演示算法思路，这是我当时的指导老师说的虽然我到现在都不知道清晰到底是哪里清晰了。编译器无非是锦上添花，大佬用notepad都能写，当然编译器的代码补全好用的一批。
大佬说刷算法就要从二叉树开始，然后给了一个二叉树中的最大路径和
然后我就开始看着leetcode里面给的一堆东西开始发愁……
截图1
上面那一块绿的是啥？codeforces里都是直接给一块编辑器然后自己从头开始写，所以我先要花时间弄明白这上面的那一块都在表示什么。
首先他是新建了一个结构体TreeNode
然后是新建了int型变量为val数据域
定义了指向左右节点的指针left和right或者也可以叫做左子树和右子树
构造了一个无参函数TreeNode()
构造了一个有参函数TreeNode(int x)其中的参数是给到了val，左子树和右子树还是空的
构造了一个有参函数TreeNode(int x, TreeNode *left, TreeNode *right)三个参数都给到了相应的值。
嗯……然后那么就是可以直接用到他上面给的结构体里的东西直接开始编译了，不得不说确实简单了很多。
下面看一下题目介绍
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例1
示例2
所以就是题目的整个意思就是：给了我们一棵树，其次我们只需要首先遍历一遍二叉树确定其中的节点联系，最后把节点联系最大的那一组路径和输出就可以了。
所以我们所要编写的程序就是一个二叉树的遍历。
那么是前序遍历还是中序遍历还是后序遍历？
简单说一下前中后的区别：
- 前序遍历是指到一个节点后，马上输出该节点的值，然后继续遍历左右子树
- 中序遍历是指到一个节点后，将该节点的值暂存，在遍历完左子树后输出该节点的值，然后继续遍历右子树。
- 后序遍历是指到一个节点后，将该节点的值暂存，在遍历完左右子树后输出该节点的值。
看一下题目，要求最大路径和，那就是每到一个节点，遍历完它的左右子树，然后把它的值加一加。
开始写代码！！！
但是这个简书自带的编辑器下写代码没有自动缩进，所以直接在编译器里写吧……
下面贴一下通过代码：
class Solution {
int big = INT_MIN;//给个最小整数值
public:
int onesidemax(TreeNode* root){
if (root == nullptr) return 0;
int left = max(0, onesidemax(root->left));//左子树的最大值
int right = max(0, onesidemax(root->right));//右子树的最大值
//后序遍历
big = max(big, left+ right+ root->val);//更新答案
return max(0, max(left, right)) + root->val;
}
int maxPathSum(TreeNode* root){
onesidemax(root);
return big;
}
};
解题详情具体看代码内注释，果然有了代码高亮整个人都好起来了。
网友评论