基础树相关题

二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

本题的关键点在于每个点至多出现一次，每个节点可能会连接三个点，因此只能选择其中两个点连接，不然该点就被两条路径使用了。可以选择的情况有：

1. 父节点 + 左
2. 父节点 + 右
3. 左 + 右

实际上前两种可以看作一种情况，使用递归来解决，当递归返回的时候，左右子树的最大路径和已经确定，那么第三种情况的答案可以直接得到，前两种还需要回溯到父节点处理，于是在递归的过程中有临时最大值和全局最大值。使用参数来保存全局最大，函数返回当前的局部最大（前两种情况才需要返回，第三种不需要父节点）。

void dfs(TreeNode* root, int &res) {
    if (!root) return ;
    int l = dfs(root, res), r = dfs(root, res);
    // 计算三种情况
    int par = root->val + max(0, max(l, r));
    int nopar = root->val + max(max(0, l) + max(0, r));
    return max(0, max(par, nopar));
}

int maxPathSum(TreeNode* root) {
    // 节点在路径中最多出现一次，而一个节点可能连接三个点，因此有三种情况，连接父节点+左、父节点+右、左+右
    int res = INT_MIN;
    dfs(root, res);
    return res;
}