一 题目描述
124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
二 实例讲解
image.png
三 思路
1.对每一个节点都计算出：有穿过太但不穿过它父节点的最大路径和
2.整体最大路径和：1中所有计算结果的最大值
image.png
- 假设S(L)是穿过L节点但不穿过它父节点的最大路径和
- 假设V(k)是节点K能提供给父节点的最大路径值
image.png
3.1 思路1-如何求1个节点能提供给父节点的最大路径值
image.png
由此可见，求一个节点能提供给父节点的最大路径值，需要采取后序遍历
左-右-root
四 代码实现
4.1 求一个节点能提供给父节点的最大路径值
/// 求一个节点能提供给父节点的最大路径值
- (int)value:(TreeNode *)node {
if (node == nil) {
return 0;
}
int leftV = MAX([self value:node.left], 0); // 左子树节点最大路径值
int rightV = MAX([self value:node.right], 0); // 右子树节点最大路径值
return node.value + MAX(leftV, rightV);
}
4.2 求最大路径和
static NSInteger sum = 0;
- (int)maxPathSum:(TreeNode *)root {
[self value1:root];
return sum;
}
/// 求最大路径和
- (int)value1:(TreeNode *)node {
if (node == nil) {
return 0;
}
int leftV = MAX([self value1:node.left], 0); // 左子树节点最大路径值
int rightV = MAX([self value1:node.right], 0); // 右子树节点最大路径值
// 路径累计求和
sum = MAX(sum, node.value + leftV + rightV);
NSLog(@"value = %d,sum = %d",node.value, sum);
return node.value + MAX(leftV, rightV);
}
- 运行结果
2019-11-26 22:17:53.264435+0800 03_CheckIsValidBSTTree[9803:359884] 11
2019-11-26 22:17:53.264599+0800 03_CheckIsValidBSTTree[9803:359884] value = 1,sum = 1
2019-11-26 22:17:53.264698+0800 03_CheckIsValidBSTTree[9803:359884] value = 3,sum = 3
2019-11-26 22:17:53.264812+0800 03_CheckIsValidBSTTree[9803:359884] value = 2,sum = 6
2019-11-26 22:17:53.264918+0800 03_CheckIsValidBSTTree[9803:359884] value = 5,sum = 6
2019-11-26 22:17:53.265004+0800 03_CheckIsValidBSTTree[9803:359884] value = 4,sum = 14
2019-11-26 22:17:53.265090+0800 03_CheckIsValidBSTTree[9803:359884] value = 8,sum = 14
2019-11-26 22:17:53.265173+0800 03_CheckIsValidBSTTree[9803:359884] value = 10,sum = 14
2019-11-26 22:17:53.265264+0800 03_CheckIsValidBSTTree[9803:359884] value = 12,sum = 14
2019-11-26 22:17:53.265345+0800 03_CheckIsValidBSTTree[9803:359884] value = 11,sum = 33
2019-11-26 22:17:53.265422+0800 03_CheckIsValidBSTTree[9803:359884] value = 9,sum = 40
2019-11-26 22:17:53.265586+0800 03_CheckIsValidBSTTree[9803:359884] value = 7,sum = 48
2019-11-26 22:17:53.265773+0800 03_CheckIsValidBSTTree[9803:359884] maxSum = 48
本文参考MJ老师的每周一道算法题，非常感谢
