1回答

liuyubobobo

2019-08-10

已采纳

两次dfs。

第一次dfs，求出从以每一个节点为初始，向左或者向右的一条路径，路径的最大值。

第二次dfs，求出经过每一个节点，左边延展一条路径，右边延展一条路径，这个整体路径（这是题意定义的Path）的最大值。

第二次dfs得到的就是结果。

参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0124-Binary-Tree-Maximum-Path-Sum/cpp-0124/main.cpp

其实这两次dfs可以合并在一趟中完成。

参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0124-Binary-Tree-Maximum-Path-Sum/cpp-0124/main2.cpp

继续加油！：）

0

1

weixin_慕数据6497584

谢谢老师！

2019-08-10

共1条回复