1 二叉树的前中后序遍历（前：根-左-右，中：左-根-右，后：左-右-根）

二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

来源：力扣（LeetCode）

解题思路：（1）找值最大的路径，从局部到整体，从小节点到大线条，先找到角落最大，在逐步向外扩充；——遇见更大的值，替换当前值；

                  （2）先走到最底层的节点，先访问子节点，再一点点向上去扩充最大值；——递归思想

                  （3） 有可能走遍大江南北，发现自己最初走的小路才是收益最大的，有可能这条小路不被别人所肯定，各种因素下，你不得不去尝试，不去外边走走，不知道自己其实很优秀，要相信自己；——时刻保存自己曾经的最大值

                  注意（1）如果只有一个节点，不管它的值是正数还是负数，它就是最大值；

                         （2）有多个节点时候，我们允许途经负数值的节点，但是不需要从负数值的起点开始走，不允许最后一个路径节点是负值，这也是它题目说的任意节点，不一定是子节点；

/**
 * 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 SearchMax(int& Maxval ,TreeNode *root)
    {
          //先找局部最大，在逐渐选择一条路去外部扩充
           //保存自己走过的路的最大值，因为有可能去外边扩展回来发现还没有最开始走的那条路财富值最多，但是一定要尝试
           if(root == nullptr)//1root本身是空节点，2最底层子节点不在有左右子树，需要一个停止条件
           {
               return 0;
           }
           //先找局部最大，就是先找最小的子树的值，一般是按照先看看左节点，再看看右节点
           //注意我们允许中间经过负数的节点，但是不需要首尾节点是负数；如果中间经过某个负数节点之后和是负数，那这个支路可以废弃了
            int leftvalue = max(0,SearchMax(Maxval,root->left));
            int rightvalue = max(0,SearchMax(Maxval,root->right));
           //记录临时局部最大值
           Maxval = max(Maxval,leftvalue+rightvalue +root->val);
           //选择半条当前最大的路，尝试去扩展
            return max(leftvalue,rightvalue)+root->val;

    }
    int maxPathSum(TreeNode* root) {
        //真正的最大路径值 
        int MaxValue= -1000;//如果存在一个或多个负数节点，最小值是-1000
        //根节点的左路最大值，右路最大值，+根节点的值
        SearchMax(MaxValue,root);//不需要无意义的返回值声明，赋值；会影响性能
        // int x = searchmax(val,root);（一句赋值需要好几毫秒的时间）
        return MaxValue;
    }
};