今天向大家介绍一道二叉树的题目，题目问题比较新颖，我自己在做题的过程中也碰到了些问题，花了些时间才通过测试题的。在这里向大家介绍一下思路。
题目如下：二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。具体题目描述可以参考引文1。
这道题目的具有最大路径和的路径的特点为：1、是任意的二叉树，二叉树的节点的值没有规律；2、最大的路径除了根节点允许同时拥有左右子孩子外，其它节点只允许只有一个孩子(左孩子或右孩子，因为每对相邻节点之间都存在一条边，如果非根节点同时有左孩子和右孩子，则不满足相邻节点之间有边的情况）。3，最大路径有可能只有一个节点，也有可能这条路径的节点都属于树的非叶子节点。
总体思路采用类似于树的后序遍历算法，算法逻辑可以描述大体如下：1、如果为叶子节点，直接返回该节点的值；2、如果该节点只有左孩子，则递归调用左孩子返回最大的路径和max_left，这个路径和放入最大路径和的candidates里边，同时该节点值本身也放入candidates里边（是否冗余可能需要再确认一下），如果max_left大于0，则返回max_left + root->val;否则返回root->val。类似的情况是节点只有右孩子，不做过多阐述；3、节点同时具有左孩子和右孩子，则分别递归调用左孩子和右孩子的最大路径和函数返回值max_left,max_right。并将max_left,max_right中的大者max_left_right放入candidates，同时将max_left + root->val+max_right作为candidates，以及如果max_left_right大于0，则返回max_left_right+root->val的值作为root的调用函数以root节点作为参数的返回值。否则如果max_left_right小于0，则直接返回root->val的值作为以root的参数的调用函数的返回值。具体代码请参考引文2的实现
References
Leave a Reply