LC 124 Binary Tree Maximum Path Sum 解题思路

Question

Bobo老师您好，
想请教一下您lc124这道题的解题思路。 谢谢老师。

Answer 1

liuyubobobo 2019-08-10 02:57:11

两次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

继续加油！：）

• 提问者 weixin_慕数据6497584 #1

  谢谢老师！