本文主要是介绍剑指offer24：二叉树中和为某一值的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
示例1
输入
{10,5,12,4,7},22
返回值
[[10,5,7],[10,12]]
思路：使用带追溯路径的递归方法。 需要用到两个变量，一个变量用于追溯递归路径，一个变量用于记录满足条件的所有结果。
1.通过一个共享列表的pop和append的实现。优点：所有递归的栈都使用同一个列表可以减少内存消耗。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:# 返回二维列表，内部每个列表表示找到的路径def FindPath(self, root, expectNumber):# write code hereres = []path = []def recur(root, tar):if not root:returnpath.append(root.val)tar -= root.valif (tar == 0) and not root.left and not root.right:res.append(list(path))recur(root.left, tar)recur(root.right, tar)path.pop()recur(root, expectNumber)return res
2.通过为每一层递归加一个额外存储单元实现。好像没啥优点，缺点问题更大，尤其是当递归层数多的时候占用内存更大。
class Solution:# 返回二维列表，内部每个列表表示找到的路径def FindPath(self, root, expectNumber):if not root:return []result = []path = [root.val]self.sums = expectNumberself.DFS(root,result,path)return resultdef DFS(self,root,result,path):if root.left == None and root.right == None and sum(path) == self.sums:result.append(path)if root.left != None:self.DFS(root.left,result,path+[root.left.val])if root.right != None:self.DFS(root.right,result,path+[root.right.val])
#题目来源于牛客网：https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
这篇关于剑指offer24：二叉树中和为某一值的路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
