二叉樹中的最大路徑和

遞歸和動態(tài)規(guī)劃，都是可以分解為一系列子問題求解，然后由子問題得到整個問題的解。對于這個題目，因為要求最大路徑和，因此需要計算經(jīng)過每個節(jié)點的最大路徑和，然后才能獲得其中路徑和最大的那一條。

對于一個節(jié)點root，求經(jīng)過該節(jié)點的最大路徑和，可以以該節(jié)點作為分隔，將這條路徑分為兩部分，一部分以其左孩子作為起始點向下的路徑，另一部分以其右孩子作為起始點向下的路徑。因此就產(chǎn)生了子問題。當求經(jīng)過root節(jié)點的最大路徑和時，先求解：

1. 以其左孩子為起始點的最大路徑和（方向向下）。

2. 以其右孩子為起始點的最大路徑和（方向向下）。

3. 然后再得到經(jīng)過該節(jié)點的最大路徑和。

最長同值路徑

原理同上。

二叉樹的直徑

原理同上。