Java&C++题解与拓展——leetcode508.出现次数最多得子树元素和【么的新知识】

• 题目要求
• 思路：DFS
• • Java
  • C++
  • Rust
• 总结

• 遍历整棵树，计算每一个节点的子树元素和，放入哈希表（去重+计数），同时记得维护一个最大值用以构造答案。

【论一道DFS模拟题怎么编出一段文字叙述的题解】

class Solution {
    Map map = new HashMap<>();
    int maxv = 0;
    int DFS(TreeNode root) {
        // 遍历计算子树元素和
        if (root == null)
            return 0;
        int cur = root.val + DFS(root.left) + DFS(root.right);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        maxv = Math.max(map.get(cur), maxv); // 维护最大值
        return cur;
    }
    public int[] findFrequentTreeSum(TreeNode root) {
        DFS(root);
        // 构造答案
        List list = new ArrayList<>();
        for (int vlu : map.keySet()) {
            if (map.get(vlu) == maxv)
                list.add(vlu);
        }
        int n = list.size();
        int[] res = new int[n];
        for (int i = 0; i < n; i++)
            res[i] = list.get(i);
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

class Solution {
    unordered_map map;
    int maxv = 0;
public:
    int DFS(TreeNode *root) {
        // 遍历计算子树元素和
        if (root == nullptr)
            return 0;
        int cur = root->val + DFS(root->left) + DFS(root->right);
        map[cur] = map[cur] + 1;
        maxv = max(map[cur], maxv); // 维护最大值
        return cur;
    }
    vector findFrequentTreeSum(TreeNode* root) {
        DFS(root);
        // 构造答案
        vector res;
        for (auto &[vlu, cnt] : map) {
            if (cnt == maxv)
                res.push_back(vlu);
        }
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
    fn DFS(root: Rc>, map: &mut HashMap) -> i32 {
        // 遍历计算子树元素和
        let cur = if root.borrow().left.is_none() && root.borrow().right.is_none() {
            root.borrow().val
        } else {
            let mut cur = root.borrow().val;
            if root.borrow().left.is_some() {
                let rl = root.borrow().left.clone().unwrap();
                cur += Solution::DFS(rl, map);
            }
            if root.borrow().right.is_some() {
                let rr = root.borrow().right.clone().unwrap();
                cur += Solution::DFS(rr, map);
            }
            cur
        };
        map.insert(cur, *map.get(&cur).unwrap_or(&0) + 1);
        cur
    }
    pub fn find_frequent_tree_sum(root: Option>>) -> Vec {
        let mut map = HashMap::new();
        Solution::DFS(root.unwrap(), &mut map);
		// 构造答案
        let mut maxv = 0;
        let mut res = vec![];
        map.iter().for_each(|(&vlu, &cnt)| {
            if cnt > maxv {
                maxv = cnt;
                res = vec![vlu]
            }
            else if cnt == maxv {
                res.push(vlu);
            }
        });
        res
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

看到树了不来个DFS都说不过去，遍历顺便计算子树元素和，这题没想到卡在了Java的返回值，还要绕一步再构造数组。

又在rust的borrow、clone、unwrap各种里绕了半天。