508. 出现次数最多的子树元素和

分手后的思念是犯贱 2022-10-07 14:56 45阅读 0赞

> **给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。**
> 
> **你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。**
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        HashMap<Integer,Integer> map=new HashMap();//装的是 元素和,当前元素和出现的次数
         int max=1;//最大的次数
        public int[] findFrequentTreeSum(TreeNode root) {
            /**
            超简单题  递归+哈希表即可
             */
            helper(root);
            Set<Map.Entry<Integer,Integer> > set=map.entrySet();
            Iterator<Map.Entry<Integer,Integer>> iter=set.iterator();
            List<Integer> list=new ArrayList();//结果集
          
           
            while(iter.hasNext()){
               Map.Entry<Integer,Integer> ele= iter.next();//单独保存一下 否则两次.next()会越界
                if(ele.getValue()==max){
                    list.add(ele.getKey());
                }
            }
            Integer[] arr = list.toArray(new Integer[list.size()]);//list转数组,必须转为包装类型
            return Arrays.stream(arr).mapToInt(Integer::valueOf).toArray();
            //把Integer数组转为int数组  用到了流,JDK1.8新特性,如果不会刻意使用最笨的方法一边遍历 一边转换
           
        }
        public int helper(TreeNode root){
            if(root==null){
                return 0;
            }
    
            int left=helper(root.left);
            int right=helper(root.right);
            int sum=left+right+root.val;
            map.put(sum,map.getOrDefault(sum,0)+1);//更新元素和,和他出现的次数
            max=Math.max(max,map.get(sum));//跟新最大值
            return sum;//返回当前的元素和
        }
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/20c00bcb8c384e079d647bc828cf36b7.png