专栏：50多种数据结构彻底征服。
专栏：50多种经典图论算法全部掌握。
今天在牛客网上看到一张图片，展示的是各互联网大厂的月薪分布，从分布结果来看，50K以上占比最高的是字节和拼多多。30~50k占比最高的是贝壳，其次是阿里，现在不是房价都降了吗，贝壳工资怎么还这么高？
图片来源：牛客网
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第113题：路径总和 II。
问题描述
来源：LeetCode第113题
难度：中等
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
示例1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例2：
输入：root = [1,2,3], targetSum = 5 输出：[]
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
问题分析
这题和昨天讲的路径总和类似，昨天讲的只要满足从根节点到叶子节点路径上的节点和等于targetSum即可。而这题是让找出所有从根节点到叶子节点路径和等于targetSum的路径。
我们从根节点开始，记录遍历路径上的所有节点，到叶子节点的时候如果路径上的节点和等于targetSum，就把这条路径记录下来。
注意路径的保存使用的是引用传递，最后还需要回溯，就是在递归往回走的时候把最后添加的给移除。
JAVA：
public List
> pathSum(TreeNode root, int targetSum) { List > ans = new ArrayList<>(); // 存放结果的集合 List path = new ArrayList<>(); // 存放从根节点到叶子节点的值 dfs(root, targetSum, path, ans); // dfs遍历 return ans; } public void dfs(TreeNode cur, int targetSum, List path, List > ans) { if (cur == null) // 节点为空，直接返回 return; path.add(cur.val); // 把当前节点的值添加到路径path中 // 如果是叶子节点，当前路径上的和等于targetSum，就把当前路径添加进来 if (cur.left == null && cur.right == null && targetSum == cur.val) { ans.add( new ArrayList<>(path)); } else { // 沿着当前树的左右子节点往下遍历，这里要注意targetSum的值要减去当前节点的值 dfs(cur.left, targetSum - cur.val, path, ans); dfs(cur.right, targetSum - cur.val, path, ans); } path.remove(path.size() - 1); // 回溯，把最后一个添加的节点给移除 }C++：
public:
vector
> pathSum(TreeNode *root, int targetSum) { vector
> ans;// 存放结果的集合 vector
path;// 存放从根节点到叶子节点的值 dfs(root, targetSum, path, ans);// dfs遍历 return ans; } void dfs(TreeNode *cur, int targetSum, vector
&path, vector
> &ans) { if (!cur)// 节点为空，直接返回 return; path.push_back(cur->val);// 把当前节点的值添加到路径path中 // 如果是叶子节点，当前路径上的和等于targetSum，就把当前路径添加进来 if (!cur->left && !cur->right && targetSum == cur->val) { ans.push_back(path); } else { // 沿着当前树的左右子节点往下遍历，这里要注意targetSum的值要减去当前节点的值 dfs(cur->left, targetSum - cur->val, path, ans); dfs(cur->right, targetSum - cur->val, path, ans); } path.pop_back();// 回溯，把最后一个添加的节点给移除 }
Python：
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(cur, targetSum):
if not cur: # 节点为空，直接返回
return
path.append(cur.val) # 把当前节点的值添加到路径path中
# 如果是叶子节点，当前路径上的和等于targetSum，就把当前路径添加进来
if not cur.left and not cur.right and targetSum == cur.val:
ans.append(path[:])
else:
# 沿着当前树的左右子节点往下遍历，这里要注意targetSum的值要减去当前节点的值
dfs(cur.left, targetSum - cur.val)
dfs(cur.right, targetSum - cur.val)
path.pop() # 回溯，把最后一个添加的节点给移除
ans = [] # 存放结果的集合
path = [] # 存放从根节点到叶子节点的值
dfs(root, targetSum) # dfs遍历
return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴