题意分析

  • 这个题目我们需要计算出一棵二叉树上面的所有的路径当中，找出路径的和最大的那个值。
  • 这个题目的难点就是中途可能会存在权值为负数的情况，还有权值为0的情况不好处理。
  • 这个题目还是有点意思的，我们可以用一个类似与树形DP的方法进行求解。
  • 前缀知识，树形DP，树形DP就是我们假设我们知道了一棵二叉树的左右的子节点的最优值，然后我们可以传递到这个节点本身，最终传递到整棵树上面。

思路分析

解法一 DFS+树形DP

  • 对于树的题目，很大程度上都可以使用搜索进行求解。这个题目也是一样的，使用一个先序遍历的思想，当我们进行递归的时候，我们先向左右子节点进行递归，求出左右子树的最优的情况返回，然后我们就可以更新这个节点的最优的情况了。
  • 结合下面的图我们可以更好地理解我们如何进行递归。
    图片说明
  • 接下来，我们就可以结合我们的代码进行理解了。具体请看注释
    • 在进行DFS的时候可能会遍历所有的点，时间复杂度为O(n）
    • 需要存储整个树的所有的结点的情况，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    // 注意，可能会存在权值为负数的节点，所以把这个先设置为负无穷
    int ans=-0x3f3f3f3f;
    int  DFS(TreeNode* now){
        // 这个是一个叶子节点
        if(!now) return 0;
        // 递归求出左右子树的最大的路径值
        int left=DFS(now->left);
        int right=DFS(now->right);
        int nowSum=now->val;
        if(left>0) nowSum+=left;
        if(right>0) nowSum+=right;
        // 更新这个节点，这条路径是这个节点的左右子树包括这个节点本身构成的
        ans=max(ans,nowSum);

        // 向上传递的时候只能三种方式进行传递
        // 左+中，右+中，中这三种方法
        return max(now->val,max(left,right)+now->val);
    }
    int maxPathSum(TreeNode* root) {
        // write code here
        ans=max(ans,DFS(root));
        return ans;
    }
};

解法二 BFS

  • 和上面的DFS的思路一样，我们使用BFS进行求解，我们可以使用队列来进行一个层序遍历。我们先把这些结果都放到一个动态数组里面，然后我们从后往前面开始进行遍历，这其实就是我们从叶子节点到根节点开始进行访问，模拟了一个树形DP的一个过程。不断从叶子节点更新到根节点的，维护最终的答案。
  • 代码如下
    • 在进行BFS的时候可能存在遍历到所有的结点的信息的情况，时间复杂度为O(n)
    • 需要对所有的结点的信息进行存储，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    vector<TreeNode*> node;
    int ans=-0x3f3f3f3f;
    queue<TreeNode*> q;
    int maxPathSum(TreeNode* root) {
        // write code here
        if(!root){
            return 0;
        }
        q.push(root);
        // 进行一个层序遍历求出从根节点到叶子节点的所有节点
        while(!q.empty()){
            TreeNode* now=q.front();
            q.pop();
            node.push_back(now);
            if(now->left) q.push(now->left);
            if(now->right) q.push(now->right);
        }
        // 从后往前开始遍历
        for(int i=node.size()-1;i>=0;i--){
            TreeNode* now=node[i];
            // 如果这个是叶子节点，那么直接比较
            if(now->left==NULL&&now->right==NULL){
                ans=max(ans,now->val);
            }else{
                // 不是叶子节点的情况，这个时候我们的左右子节点的最优值已经求出
                int left=0,right=0;
                if(now->left){
                    left=now->left->val;
                }
                if(now->right){
                    right=now->right->val;
                }
                int nowSum=now->val;
                // 更新这个节点的最优值，要用于向上进行传递
                now->val=max(now->val,max(left,right)+nowSum);
                // 更新答案
                ans=max(ans,max(now->val,left+right+nowSum));
            }
        }
        return ans;
    }
};