LeetCode124二叉树中的最大路径和

Posted on | | Visitors:
Words count in article: 503 字 | Reading time ≈ 2 分

题目链接

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

题解

  • 递归解法
  • 路径：一条从树中任意结点出发，达到任意结点的序列。该路径至少包含一个结点，且不一定经过根结点。
  • 这道题和LeetCode687最长同值路径和LeetCode543二叉树的直径很相似，都很难，每个题都做了很久
    • 三道题的共性是dfs函数并非直接实现了目标功能，而是将目标功能拆解，实现目标功能的一部分，然后再利用某种关系（根结点、左子树、右子树之间的关系，需要结合题意）拼接出目标功能（求目标值）
  • 思路见代码注释
  • 需要高度注意dfs函数的功能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Problem: LeetCode 124
// URL: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
// Tags: Tree Recursion DFS
// Difficulty: Hard

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution
{
private:
    int maxSum = INT_MIN; // 全局最大路径和

    // 功能：求一颗树的最大路径和，要求从根结点开始，在左子树或右子树结束，也可不经过左子树和右子树，即至多经过一个子树
    int dfs(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        // 过程中更新全局最大路径和：根结点必须经过，左右子树可经过可不经过
        maxSum = max(maxSum, root->val + max(left, 0) + max(right, 0));
        // 从根结点开始，在左子树或右子树结束，也可不经过左子树和右子树，即至多经过一个子树
        return max(root->val, root->val + max(max(left, right), 0));
    }

public:
    // 求一颗树的最大路径和，不要求经过根结点，起始和终止结点任意
    int maxPathSum(TreeNode *root)
    {
        dfs(root);
        return this->maxSum;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!