递归，最优
题目
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例1
输入：[1,2,3]
1
/ \
2 3
输出：6
示例2
输入：[-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出：42
题解
思路
路径每到一个节点，有 3 种选择：1. 停在当前节点。2. 走到左子节点。3. 走到右子节点。
走到子节点，又面临这 3 种选择，可以用递归。
注意！不能走进一个分支又掉头回来走另一个分支，路径会重叠。
定义递归函数
首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
具体而言，该函数的计算如下。
- 空节点的最大贡献值等于 0。
- 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
一个子树内部的最大路径和 = 左子树提供的最大路径和 + 根节点值 + 右子树提供的最大路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
from queue import Queue
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def create_tree(list_tree):
if not list_tree:
return []
new_queue= Queue()
root = TreeNode(list_tree[0])
new_queue.put(root)
count = 1
while not new_queue.empty() and count<len(list_tree):
dequeue = new_queue.get()
if not dequeue.left and not dequeue.right:
if count<len(list_tree) and list_tree[count]:
dequeue.left=TreeNode(list_tree[count])
count= count+1
if count<len(list_tree) and list_tree[count]:
dequeue.right=TreeNode(list_tree[count])
count= count+1
if dequeue.left:
new_queue.put(dequeue.left)
if dequeue.right:
new_queue.put(dequeue.right)
return root
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
priceNewpath = node.val + leftGain + rightGain
self.maxSum = max(self.maxSum, priceNewpath)
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum
|
1
2
3
4
5
| root = [-10,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.maxPathSum(root_tree)
print(result)
|
42
