二叉树中的最大路径和

递归和动态规划，都是可以分解为一系列子问题求解，然后由子问题得到整个问题的解。对于这个题目，因为要求最大路径和，因此需要计算经过每个节点的最大路径和，然后才能获得其中路径和最大的那一条。

对于一个节点root，求经过该节点的最大路径和，可以以该节点作为分隔，将这条路径分为两部分，一部分以其左孩子作为起始点向下的路径，另一部分以其右孩子作为起始点向下的路径。因此就产生了子问题。当求经过root节点的最大路径和时，先求解：

1. 以其左孩子为起始点的最大路径和（方向向下）。

2. 以其右孩子为起始点的最大路径和（方向向下）。

3. 然后再得到经过该节点的最大路径和。

最长同值路径

原理同上。

二叉树的直径

原理同上。