二叉树中的最大路径和

[编程题]二叉树中的最大路径和

热度指数：73629 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意:

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树的根节点root，请你计算它的最大路径和

例如：
给出以下的二叉树，

最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6

数据范围：节点数满足 $1 \le n \le 10^5$ ，节点上的值满足 $|val| \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

示例2

输入

{-20,8,20,#,#,15,6}

输出

说明


其中一条最大路径为:15=>20=>6，路径和为15+20+6=41

示例3

输入

{-2,#,-3}

输出

-2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

陈GUOSHI

static int max(int a , int b) {
return a > b ? a : b ;
}

static int max_value = 0;

int maxPathSumWithValue(struct TreeNode *root)
{

if (root == NULL)
{
return 0;
}
max_value = max(root->val, max_value);
if (root->left == NULL && root->right == NULL) {
return root->val;
}
int left_node_val = maxPathSumWithValue(root->left);
int right_node_val = maxPathSumWithValue(root->right);
int max_node_val = max(max(left_node_val, right_node_val), left_node_val + right_node_val);
if (max_node_val >= 0 && (root->val + max_node_val >= max_value))
{
max_value = root->val + max_node_val;
}
int add_val = max(max(left_node_val, right_node_val), 0);
return root->val + add_val;
}

int maxPathSum(struct TreeNode *root)
{
if (root == NULL)
{
return 0;
}
max_value = root->val;
maxPathSumWithValue(root);
return max_value;
}

发表于 2022-01-21 22:40:25 回复(0)