题目描述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

思路

详见链接

代码

class Solution:def pathSum(self, root:TreeNode, sum:int)->List[List[int]]:res, 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, sum)return res

复杂度

时间复杂度 O(N)：NN为二叉树的节点数，先序遍历需要遍历所有节点。

空间复杂度 O(N) ：最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。

如果觉得《剑指offer面试题34. 二叉树中和为某一值的路径(先序遍历)(回溯)》对你有帮助，请点赞、收藏，并留下你的观点哦！