二叉树最大路径和

从顶点到叶节点的一条路径，使得路径上节点的值得和最大。

如图所见，一个二叉树，各结点值是int类型，现在要找出各结点之和最大的路径。

如图可知，此二叉树有三条路径：[1,2,4], [1,2,5], [1,3]

结点之和最大的是[1,2,5]，我们最终的目标就是要找到这条路径！

分析下先序遍历的路径：1->2->4->5->3

问题求解

• 当发现到达叶子结点时，确认一条路径，并将这路径中各结点相加得到sum，然后退回至父结点再次寻找另其它叶子结点，重复之前的操作，并与上次的sum进行比较...
• 如此重复下去，直至所有路径都遍历完成，sum保存的就是结点之和最大的值。
• sum的路径用栈保存，栈顶叶子结点，栈底根结点

struct TreeNode {
    TreeNode *left;
    TreeNode *right;
    int value;
};

vector<TreeNode *> path;

// cur:当前节点
int solve(TreeNode *cur) {
    if (cur->left && !cur->right) {
        path.push_back(cur->left);
        return cur->value + solve(cur->left);
    } else if (!cur->left && cur->right) {
        path.push_back(cur->right);
        return cur->value + solve(cur->right);
    } else if (cur->left && cur->right) {
        int a = solve(cur->left);
        int b = solve(cur->right);
        if (a > b) {
            path.push_back(cur->left);
            return cur->value + a;
        } else {
            path.push_back(cur->right);
            return cur->value + b;
        }
    } else if (!cur->left && !cur->right) {
        return cur->value;
    }
}