給定一個(gè)非空二叉樹盈滴，返回其最大路徑和偿洁。
本題中撒汉，路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，達(dá)到任意節(jié)點(diǎn)的序列涕滋。該路徑至少包含一個(gè)節(jié)點(diǎn)睬辐，且不一定經(jīng)過根節(jié)點(diǎn)。
示例 1:
一開始我是這樣的思路宾肺，從左右子樹中獲取最大的路徑和的值溯饵，返回給left,right，然后從left,right,left+right+val,val中取最大值锨用，但是這樣會(huì)有一個(gè)問題丰刊，在只有2個(gè)節(jié)點(diǎn)的樹中若值都為負(fù)數(shù)，那么由于有一個(gè)空樹增拥，返回的最大值是0會(huì)導(dǎo)致最后的結(jié)果出錯(cuò)啄巧。
看了一些網(wǎng)上的解答，思路都和我差不多跪者，都有共同的錯(cuò)誤棵帽。查看一些優(yōu)秀的解答
他是這樣的思路：
在遞歸函數(shù)中，如果當(dāng)前結(jié)點(diǎn)不存在渣玲，那么直接返回0。否則就分別對(duì)其左右子節(jié)點(diǎn)調(diào)用遞歸函數(shù)弟晚，由于路徑和有可能為負(fù)數(shù)忘衍，而我們當(dāng)然不希望加上負(fù)的路徑和，所以我們和0相比卿城，取較大的那個(gè)枚钓，就是要么不加，加就要加正數(shù)瑟押。然后我們來更新全局最大值結(jié)果res搀捷，就是以左子結(jié)點(diǎn)為終點(diǎn)的最大path之和加上以右子結(jié)點(diǎn)為終點(diǎn)的最大path之和，還要加上當(dāng)前結(jié)點(diǎn)值多望，這樣就組成了一個(gè)條完整的路徑嫩舟。
[LeetCode] Binary Tree Maximum Path Sum 求二叉樹的最大路徑和 - Grandyang - 博客園
修改我們的程序：
