leetcode 124. Binary Tree Maximum Path Sum 最大路径和 + DFS深度优先搜索

缺乏、安全感 2022-06-08 04:55 151阅读 0赞

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:  
Given the below binary tree,

1
      / \
     2   3

Return 6.

这道题求的是通过父子关系连接起来的最大的路径和，路径的起始结点不一定是叶子节点。

我看了这道题好久才明白，那么我们可以利用DFS深度优先搜索来得到左右结点的最大sum，然后更新最大的路径sum。

建议和[leetcode 437. Path Sum III 深度优先遍历DFS][leetcode 437. Path Sum III _DFS] 和[leetcode 687. Longest Univalue Path 深度优先遍历DFS][leetcode 687. Longest Univalue Path _DFS] 一起学习

代码如下：

/*class TreeNode 
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    
    /*
     * 函数递归返回的是某一路径的最大sum
     * 那么对于某一个结点，更新相关详细即可
     * 如果只是一个节点,那么当然就是这个节点的值了.
     * 
     * */
    public class Solution
    {
        int MaxPathSum = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) 
        {
            maxPathSumByRecursion(root);
            return MaxPathSum;
        }
    
        public int maxPathSumByRecursion(TreeNode root) 
        {
            if(root==null)
                return 0;
            else
            {
                int leftMax = maxPathSumByRecursion(root.left);
                int rightMax = maxPathSumByRecursion(root.right);
                int tmp = root.val;
                if(leftMax>0)
                    tmp += leftMax;
                if(rightMax>0)
                    tmp += rightMax;
                //这里更新最大路径值
                MaxPathSum = Math.max(MaxPathSum, tmp);
    
                //这里返回的是当前左孩子或者右孩子的最大的sum，并不是某一条路径的最大sum
                return Math.max(root.val, Math.max(leftMax + root.val, rightMax + root.val));
            }
        }
    }

下面手C++的做法，就是DFS深度优先遍历的做法，这里要注意两个问题：  
我们是用DFS递归来计算某一个路径的sum，然后在递归计算中间计算比较最大的路径值

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <climits>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int maxSum = numeric_limits<int>::min();
        int maxPathSum(TreeNode* root) 
        {
            if (root == NULL)
                return 0;
            byDFS(root);
            return maxSum;
        }
    
        int byDFS(TreeNode* root)
        {
            if (root == NULL)
                return 0;
            else
            {
                int left = byDFS(root->left);
                int right = byDFS(root->right);
                int tmp = root->val;
                if (left > 0)
                    tmp += left;
                if (right > 0)
                    tmp += right;
                maxSum = max(maxSum, tmp);
                return max(root->val,max(left+root->val,right + root->val));
            }
        }
    };

[leetcode 437. Path Sum III _DFS]: http://blog.csdn.net/jackzhag_123/article/details/78752985
[leetcode 687. Longest Univalue Path _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78880772