编程题 91 /123

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

注意:

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)$

参考答案

树形dp，定义dp[i]为以 i 为根的路径最大值，那么我们只需要找到每个节点的左右孩子的dp值即可。

查看讨论

上一题下一题

扫一扫，把题目装进口袋