124二叉树中的最大路径和

末蓝、 2023-03-01 12:27 120阅读 0赞

## 一、前言 ##

标签：树\_最大路径。

问题来源LeetCode 124 难度：困难。

问题链接：[https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/][https_leetcode-cn.com_problems_binary-tree-maximum-path-sum]

## 二、题目 ##

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点

**示例1：**

输入: [1,2,3]
           1
          / \
         2   3
    输出: 6

**示例2：**

输入: [-10,9,20,null,null,15,7]
       -10
       / \
      9  20
        /  \
       15   7
    输出: 42

## 三、思路 ##

本题提供两种解决方法。

方法一：遍历每个节点，找出以该节点为根节点最大路径和，选出所有节点中最大路径和即可。

方法二：和方法一解题思想相同，方法二在方法一的基础上进行了优化，在遍历过程中找出最大的路径和。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 124_MaxPathSum.h
    * @label   : 树_最大路径
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107578859
    * @author  : niebingyu
    * @date    : 2020/07/25
    * @title   : 124.二叉树中的最大路径和
    * @purpose : 给定一个非空二叉树，返回其最大路径和。
    * 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
    *
    * 示例1：
    * 输入: [1,2,3]
    * 输出: 6
    *
    * 示例2：
    * 输入: [-10,9,20,null,null,15,7]
    * 输出: 42
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_MAXPATHSU namespace NAME_MAXPATHSU {
    #define NAMESPACE_MAXPATHSUEND }
    NAMESPACE_MAXPATHSU
    
    struct TreeNode 
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x, TreeNode* _left = nullptr, TreeNode* _right = nullptr)
            : val(x), left(_left), right(_right) {}
    };
    
    class Solution_1 
    {
    public:
        int maxPathSum(TreeNode* root) 
        {
            if (root == nullptr)
                return INT_MIN;
    
            int curMax = root->val + maxChild(root->left) + maxChild(root->right);
            int lMaxSum = maxPathSum(root->left);
            int rMaxSum = maxPathSum(root->right);
    
            return max(curMax, max(lMaxSum, rMaxSum));
        }
    
        int maxChild(TreeNode* root)
        {
            if (root == nullptr)
                return 0;
    
            static map<TreeNode*, int> memo;
            if (memo.find(root) != memo.end())
                return memo[root];
            
            if (root->left == nullptr && root->right == nullptr)
                return max(0, root->val);
            
            int curNum = root->val;
            int lMaxSum = maxChild(root->left);
            int rMaxSum = maxChild(root->right);
    
            int maxNum = max(0, max(curNum, max(curNum + lMaxSum, curNum + rMaxSum)));
            memo[root] = maxNum;
            return maxNum;
        }
    };
    
    class Solution_2 
    {
    private:
        int ans = INT_MIN;
    
    public:
        int maxPathSum(TreeNode* root) 
        {
            helper(root);
            return ans;
        }
    
        int helper(TreeNode* root) 
        {
            if(root == nullptr) return 0;
            int left = max(0, helper(root->left));
            int right = max(0, helper(root->right));
            ans = max(ans, right + left + root->val);
            return max(left,right) + root->val;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, TreeNode* root, int expect)
    {
        // 测试用例，申请的内存没有释放
        Solution_1 s;
        int result = s.maxPathSum(root);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    // 输入: [1, 2, 3]
    // 输出 : 6
    //    1
    //   / \
    //  2   3
    void Test1()
    {
        TreeNode* tn_2 = new TreeNode(2);
        TreeNode* tn_3 = new TreeNode(3);
        TreeNode* tn_1 = new TreeNode(1, tn_2, tn_3);
    
        TreeNode* root = tn_1;
        int expect = 6;
        test("Test1()", root, expect);
    }
    
    // 测试用例
    // 输入: [-10, 9, 20, null, null, 15, 7]
    // 输出 : 42
    //   -10
    //   / \
    //  9  20
    //    / \
    //  15   7
    void Test2()
    {
        TreeNode* tn_7 = new TreeNode(7);
        TreeNode* tn_15 = new TreeNode(15);
        TreeNode* tn_20 = new TreeNode(20, tn_15, tn_7);
        TreeNode* tn_9 = new TreeNode(9);
        TreeNode* tn__10 = new TreeNode(-10, tn_9, tn_20);
    
        TreeNode* root = tn__10;
        int expect = 42;
        test("Test2()", root, expect);
    }
    
    NAMESPACE_MAXPATHSUEND
    // 测试 用例 END
    //
    void MaxPathSu_Test()
    {
        cout << "------ start 124.二叉树中的最大路径和 ------" << endl;
        NAME_MAXPATHSU::Test1();
        NAME_MAXPATHSU::Test2();
        cout << "------ end 124.二叉树中的最大路径和 --------" << endl;
    }

**执行结果：**

![20200725145900145.png][]

[https_leetcode-cn.com_problems_binary-tree-maximum-path-sum]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[20200725145900145.png]: /images/20230208/5f4a8a7caebb48adb97b2a9e4ed79b16.png