树的求和属于树的题目中比较常见的，因为可以有几种变体，灵活度比较高，也可以考察到对于树的数据结构和递归的理解。
给你二叉树的根节点
root和一个表示目标和的整数targetSum，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
思路1：递归
这道题是判断是否存在从根到叶子的路径和跟给定sum相同。树的题目基本都是用递归来解决，主要考虑两个问题:
如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和等于sum 减去当前结点值的路径，只要有一个存在，那么当前结点就存在路径。
考虑结束条件是什么︰
结束条件1:如果当前节点是空的，则返回false。
结束条件2:如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
# 如果当前节点为空，则返回False
if root == None:
return False
# 如果当前节点是叶子节点，并且剩余sum等于叶子节点值
if root.left == None and root.right == None and root.val == sum:
return True
# 如果当前节点是非叶子节点，则对它的左右子树分别调用函数
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
思路2：迭代
我们可以用栈将递归转成迭代的形式。
栈中保存当前节点前的剩余值就可以了。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
# 使用栈的结构，将递归化为迭代
if root == None:
return False
# 栈
stack = [(root,targetSum)]
while stack:
node,sum = stack.pop()
# 如果为叶子节点，判断叶子节点是否满足条件
if node.left == None and node.right == None and node.val == sum:
return True
# 如果不为叶子节点，则将当前节点的孩子节点及剩余值压入栈
if node.left != None:
stack.append((node.left,sum-node.val))
if node.right != None:
stack.append((node.right,sum-node.val))
return False
这道题思路和112–路径总和是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
思路1：递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
# 需要一个辅助函数(记录变量路径)
def helper(root,sum,temp):
# 判断根节点是否是空节点
if root == None:
return None
# 如果是叶子节点，判断剩余值是否与叶子节点值相等
if root.left == None and root.right == None and root.val == sum:
temp += [root.val]
res.append(temp)
# 如果当前节点非叶子节点，则递归调用左右子树
helper(root.left,sum-root.val,temp+[root.val])
helper(root.right,sum-root.val,temp+[root.val])
res = []
helper(root,targetSum,[])
return res
思路2：迭代
在栈中添加数据结构用于保存输出路径
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
# 利用栈进行迭代
# 判断根节点是否为空节点
if root == None:
return []
res = []
tmp = []
stack = [(root,targetSum,tmp)]
while stack:
# 出栈
node,sum,tmp = stack.pop()
# 当当前节点为叶子节点且剩余值等于叶子值
if node.left == None and node.right == None and node.val == sum:
tmp += [node.val]
res.append(tmp)
# 入栈
if node.left != None:
stack.append((node.left,sum-node.val,tmp+[node.val]))
if node.right != None:
stack.append((node.right,sum-node.val,tmp+[node.val]))
return res
这道题目相比112–路径总和，增加了两个变化:
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径4 -> 9 -> 5代表数字 495
从根到叶子节点路径4 -> 9 -> 1代表数字 491
从根到叶子节点路径4 -> 0代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
思路1：递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def helper(root,nums):
if root == None:
return root
# 更新路径和
nums *= 10
nums += root.val
# 如果当前节点是叶子节点，则将nums添加到res中
if root.left == None and root.right == None:
res.append(nums)
# 递归调用左右子树
if root.left != None:
helper(root.left,nums)
if root.right != None:
helper(root.right,nums)
res = []
helper(root,0)
return sum(res)
思路2：迭代
利用栈将递归转化为迭代
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
# 判断根节点是否为空
if root == None:
return 0
# 定义一个路径，保存节点与节点值
stack = [(root,0)]
# 保存路径
res = []
while stack:
node,nums = stack.pop()
# 更新节点值
nums *= 10
nums += node.val
# 判断当前节点是否是叶子节点，如果是，则保存路径
if node.left == None and node.right == None:
res.append(nums)
# 如果当前节点非叶子节点，则将左右节点入栈
if node.left != None:
stack.append((node.left,nums))
if node.right != None:
stack.append((node.right,nums))
return sum(res)
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是15 -> 20 -> 7，路径和为 15 + 20 + 7 = 42
思路：
可以参考官方题解二叉树中的最大路径和，写的很简洁
实现一个简化的函数maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值
该函数的计算如下。
- 空节点的最大贡献值等于 0。
- 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
该函数的计算如下。对根节点调用函数
maxGain，即可得到每个节点的最大贡献值。
根据函数maxGain得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？
对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.maxSum = float('-inf') # 用于保存最大路径和
def maxPathSum(self, root: TreeNode) -> int:
# 递归计算左右节点的最大贡献值
def maxGain(node):
# 如果节点为空，则贡献值为0
if node == None:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于0时，才会选取对应子节点
left_Gain = max(maxGain(node.left),0)
right_Gain = max(maxGain(node.right),0)
# 当前节点的最大路径和等于左子树的贡献值+父节点的值+右子树的贡献值
priceNewPath = node.val + left_Gain + right_Gain
# 更新最大值
self.maxSum = max(self.maxSum,priceNewPath)
# 返回节点的最大贡献值
return node.val + max(left_Gain,right_Gain)
maxGain(root)
return self.maxSum
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例：
思路：迭代
我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是一个叶子节点，则将它对应的路径加入到答案中。如果它不是一个叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时，迭代结束。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
# 判断根节点是否为空
if root == None:
return root
# 定义队列来保存节点与路径
queue = [(root,'')]
# 用于保存结果
res = []
while queue:
size = len(queue)
for _ in range(size):
node,tmp = queue.pop(0)
tmp += str(node.val)
# 如果当前节点为叶子节点,记录路径
if node.left == None and node.right == None:
res.append(tmp)
# 格式要求
tmp += '->'
# 如果当前节点非叶子节点，则添加入队
if node.left != None:
queue.append((node.left,tmp))
if node.right != None:
queue.append((node.right,tmp))
return res
用栈实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
# 判断根节点是否为空
if root == None:
return root
# 定义栈来保存节点与路径
stack = [(root,'')]
# 用于保存结果
res = []
while stack:
node,tmp = stack.pop(0)
tmp += str(node.val)
# 如果当前节点为叶子节点,记录路径
if node.left == None and node.right == None:
res.append(tmp)
# 格式要求
tmp += '->'
# 如果当前节点非叶子节点，则添加入队
if node.left != None:
stack.append((node.left,tmp))
if node.right != None:
stack.append((node.right,tmp))
return res
如果对您有帮助，麻烦点赞关注，这真的对我很重要！！！如果需要互关，请评论或者私信！
