python -二叉树路径和为指定的值(根节点到叶子节点)

一、树前序遍历

• 前序遍历：
• • 获取所有的路径；
• 对所有的路径处理，获取每一条路径的和，输出符合条件的路径

二、递归

# 二叉树的节点的属性
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
class Solution:# 前序遍历的方式def preOrder(self, root: TreeNode, target: int) -> List[List[int]]:arr = []def dfs(root, path):if not root:returnif root.left == None and root.right == None:arr.append(path)returnif root.left:dfs(root.left, path + [root.left.val])if root.right:dfs(root.right, path + [root.right.val])returndfs(root, [root.val])_arr = []for tmp in arr:if sum(tmp) == target:_arr.append(tmp)return _arr# 递归def dfs(self, root: TreeNode, sum1: int, path: List[int]) -> List[List[int]]:arr = []def preOrder(root, sum1, path):if not root:returnif root.left == None and root.right == None and sum1 == root.val:arr.append(path)returnif root.left == None and root.right == None:returnif root.left:preOrder(root.left, sum1 - root.val, path + [root.left.val])if root.right:preOrder(root.right, sum1 - root.val, path + [root.right.val])returnpreOrder(root, sum1, [root.val])return arrdef FindPath(self, root: TreeNode, target: int) -> List[List[int]]:# write code hereif not root:return []return self.preOrder(root, target)          # 前序遍历return self.dfs(root, target, [root.val])   # 递归