124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 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
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
li=[]
if root is None:
return li
def find(root,sum,path):
sum-=root.val
if root.left is None and root.right is None and sum==0:
li.append(path+[root.val])
if root.left:
find(root.left,sum,path+[root.val])
if root.right:
find(root.right,sum,path+[root.val])
find(root,sum,[])
return li
129. 求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: return 0
self.sum = 0
def dfs(node,sum):
if node.left:
dfs(node.left,sum+str(node.left.val))
if node.right:
dfs(node.right,sum+str(node.right.val))
if not node.left and not node.right:
self.sum += int(sum)
dfs(root,str(root.val))
return self.sum
257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/
2 3
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root: return []
res = []
def helper(root, tmp):
if not root.left and not root.right:res.append(tmp + [str(root.val)])
if root.left:helper(root.left, tmp + [str(root.val)])
if root.right:helper(root.right, tmp + [str(root.val)])
helper(root, [])
return ["->".join(a) for a in res]