互联网大厂月薪分布。。。

专栏：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算法文档 。