CC

自然万物都趋向从有序变得无序

0%

leetcode-124 二叉树中的最大路径和

发表于 分类于 Valine：

124. 二叉树中的最大路径和 - 力扣（LeetCode） (leetcode-cn.com)

题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

题意

设二叉树上任意一个节点到另一个节点的路径为x，求最大的x。路径中每个节点只能出现一次

思路

贪心

贪心的想法为对于每一个节点，答案可能为四种情况

  • 当前节点的值
  • 当前节点的值+左儿子的值
  • 当前节点的值+右儿子的值
  • 当前节点的值+左儿子的值+右儿子的值

因此我们可以递归的处理二叉树，处理每一个节点的每种情况即可

代码

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
/*
 *@File Name          :leetcode-124.cpp
 *@Author             :cc
 *@Version            :1.0.0
 *@Date               :2022/3/3 9:23
 *@Description        :
 *@Function List      :
 *@History            :
 */

#include "algorithm"
#include "vector"
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int dfs(TreeNode* cur, int &ans){
        if(cur == nullptr) return 0;
        int l = dfs(cur->left, ans);
        int r = dfs(cur->right, ans);
        if(l+r+cur->val > ans) ans = l+r+cur->val;
        if(l+cur->val > ans) ans = l+cur->val;
        if(r+cur->val > ans) ans = r+cur->val;
        if(cur->val > ans) ans = cur->val;
        return max(max(l,r),0)+cur->val;
    }
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        dfs(root, ans);
        return ans;
    }
};