二叉树中的最大路径和

缺乏、安全感 2023-02-10 03:55 8阅读 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

## 三、思路 ##

对树进行深度优先遍历最长路径：包含当前结合 或 和不包含当前结点。

包含当前结点：maxPath = node.value + left + right。结点左右两边最长长度，是一条向下的路线，只能包含其左或者右子节点，不能同时包含一个父节点的左右子结点。

不包含当前结点：最长路径在当前结点左边或者右边， 在上面不用考虑，深度优先遍历会从上往下进行。不包含当前结点即为一条新的路径，newpath= node.value + left + right。

有点抽象，需要一点想象力和创造力。

## 四、编码实现 ##

//==========================================================================
    /**
    * @file : MaxPathSum.h
    * @title : 二叉树中的最大路径和
    * @purpose : 给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
    *
    * 示例 1:
    * 输入: [1,2,3]
    *
    *        1
    *       / \
    *      2   3
    *
    * 输出: 6
    * 
    * 示例 2:
    * 输入: [-10,9,20,null,null,15,7]
    *
    *    -10
    *    / \
    *   9  20
    *     /  \
    *    15   7
    *
    * 输出: 42
    *
    * 来源：力扣（LeetCode）
    * 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
    *
    */
    //==========================================================================
    #pragma once
    #include "Common.h"
    #include "ConstructTree.h"
    
    template<class T>
    int maxPathSum(BinaryTreeNode<T>* root, int& val);
    
    template<class T>
    int maxPathSum(BinaryTreeNode<T>* root)
    {
        int val = INT_MIN;
        maxPathSum(root, val);
        return val;
    }
    
    template<class T>
    int maxPathSum(BinaryTreeNode<T>* root, int& val)
    {
        if (root == nullptr) return 0;
        int left = maxPathSum(root->m_pLeft, val);
        int right = maxPathSum(root->m_pRight, val);
        int newpath = root->m_nValue + max(0, left) + max(0, right);   // 新路径 可以包含当前结点的左右孩子节点返回的最大路径。
        int ret = root->m_nValue + max(0, max(left, right));    // 对于子节点，只能包含它的左子结点或右子结点。
        val = max(val, max(newpath, ret));
        return ret;
    }
    
    // 以下为测试代码
    #define NAMESPACE_MAXPATHSUM namespace NAME_MAXPATHSUM {
    #define NAMESPACE_MAXPATHSUMEND }
    
    //
    // 测试 用例 START
    NAMESPACE_MAXPATHSUM
    
    template<class T>
    void test(const char* testName, BinaryTreeNode<T>* root, int expect)
    {
        int sum = maxPathSum(root);
        if (sum == expect)
        {
            cout << testName << " solution passed." << endl;
        }
        else
        {
            cout << testName << " solution failed. sum: " << sum << endl;
        }
    }
    
    // 根结点
    //        2        
    void Test1()
    {
        const int length = 1;
        int preorder[length] = { 2 };
        int inorder[length] = { 2 };
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        int expect = 2;
    
        test("Test1()", pRoot, expect);
    }
    
    // 完全二叉树
    //             2
    //           /   \
    //          1     3  
    void Test2()
    {
        const int length = 3;
        int preorder[length] = { 2, 1, 3 };
        int inorder[length] = { 1, 2, 3 };
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        int expect = 6;
    
        test("Test2()", pRoot, expect);
    }
    
    // 所有结点都没有右子结点
    //            5
    //           / 
    //          4   
    //         / 
    //        3 
    //       /
    //      2
    //     /
    //    1
    void Test3()
    {
        const int length = 5;
        int  preorder[length] = { 5, 4, 3, 2, 1 };
        int  inorder[length] = { 1, 2, 3, 4, 5 };
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        int expect = 15;
    
        test("Test3()", pRoot, expect);
    }
    
    // 完全二叉树
    //               4
    //            /     \
    //           2       5  
    //          / \    
    //         1   3   
    void Test4()
    {
        const int length = 5;
        int preorder[length] = { 4, 2, 1, 3, 5 };
        int inorder[length] = { 1, 2, 3, 4, 5 };
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        int expect = 14;
    
        test("Test4()", pRoot, expect);
    }
    
    //       -10
    //      /   \
    //     9    20
    //          / \
    //        15   7
    void Test5()
    {
        const int length = 5;
        int preorder[length] = { -10, 9, 20, 15, 7 };
        int inorder[length] = { 9, -10, 20, 15, 7 };
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        int expect = 42;
    
        test("Test5()", pRoot, expect);
    }
    
    NAMESPACE_MAXPATHSUMEND
    // 测试 用例 END
    //
    
    void MaxPathSum_Test()
    {
        NAME_MAXPATHSUM::Test1();
        NAME_MAXPATHSUM::Test2();
        NAME_MAXPATHSUM::Test3();
        NAME_MAXPATHSUM::Test4();
        NAME_MAXPATHSUM::Test5();
    }

**执行结果：**

![20200519234205520.png][]

[https_leetcode-cn.com_problems_binary-tree-maximum-path-sum]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[20200519234205520.png]: https://img-blog.csdnimg.cn/20200519234205520.png