hr先呛别人的，结果自己先急了。

猿大侠 · 公众号 · · 2024-07-23 12:08

正文

就业不太景气的当下，无论是找工作还是招人，大家都要心平气和的沟通，不要说不两句就开怼。最近网上一位求职者和hr怼起来了，不过我咋感觉求职者在骂自己？

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第508题：出现次数最多的子树元素和

问题描述

来源：LeetCode第508题

难度：中等

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例1：

输入 : root = [5,2,-3]

输出 : [2,-3,4]

示例2：

输入 : root = [5,2,-5]

输出 : [2]

节点数在 [1, 10^4] 范围内
-10^5 <= Node.val <= 10^5

问题分析

这题让返回出现次数最多的子树元素和，要计算二叉树的所有子树和，我们可以从下往上遍历，也就是二叉树的后续遍历。

从下往上遍历的时候就可以计算所有的子树和，把这些和保存到一个map中，最后只需要返回出现频率最高的子树和即可，计算方式和昨天讲的二叉搜索树中的众数类似。

JAVA：

int maxCount = 0;// 出现最高的次数

public int[] findFrequentTreeSum(TreeNode root) {
    Map mp = new HashMap<>();
    dfs(root, mp);
    List ans = new ArrayList<>();
    // 找出出现频率等于maxCount的，保存到list中
    for (int key : mp.keySet()) {
        if (mp.get(key) == maxCount)
            ans.add(key);
    }
    return ans.stream().mapToInt(i -> i).toArray();
}

// 后续遍历，从下往上
private int dfs(TreeNode root, Map mp) {
    if (root == null) return 0;
    int sum = dfs(root.left, mp) + dfs(root.right, mp) + root.val;
    int count = mp.getOrDefault(sum, 0) + 1;
    mp.put(sum, count);// 子树和保存到map中
    maxCount = Math.max(maxCount, count);
    return sum;
}

C++：

public:
    int maxCount = 0;// 出现最高的次数
    vector<int> findFrequentTreeSum(TreeNode *root) {
        unordered_map<int, int> mp;
        dfs(root, mp);
        vector<int> ans;
        // 找出出现频率等于maxCount的，保存到list中
        for

hr先呛别人的，结果自己先急了。

正文

请到「今天看啥」查看全文