当前位置:   article > 正文

501. 二叉搜索树中的众数(Java) leecode_java语言求二叉树里面的众数

java语言求二叉树里面的众数

在这里插入图片描述

解题思路:

二叉搜索树,考虑中序遍历,此题类似有序遍历数组。

curCount 计算当前节点出现的次数,maxCount 计算众数出现最大次数。

返回结果是数组,所以要定义一个数组储存众数。

class Solution {
    //计算众数节点的值
    LinkedList<Integer> mode = new LinkedList<>();

    int curCount = 0, maxCount = 0;
    
    TreeNode prev = null;

    public int[] findMode(TreeNode root) {

        traverse(root);
		//最后返回的数组
        int[] res = new int[mode.size()];

        for (int i = 0; i < res.length; i++){

            res[i] = mode.get(i);

        }
        
       return res;


    }

    void traverse(TreeNode root){

        if(root == null){
            return;
        }
		
		//中序遍历
        traverse(root.left);

        if(prev == null ){
        	//初始化
            curCount = 1;
            maxCount = 1;
            mode.add(root.val);

        }else{
			//节点重复
            if(prev.val == root.val){

                curCount++;
                //当前节点出现次数与最大出现次数相同,加入另外一个众数
                if(curCount == maxCount){

                    mode.add(root.val);
                    
				//当前节点出现次数大于最大出现次数 ,更新最大节点出现次数
                }else if(curCount > maxCount){

                    mode.clear();
                    maxCount = curCount;
                    mode.add(root.val);
                }
            }
			//节点不重复
            if(root.val != prev.val){

                curCount = 1;

                if(curCount == maxCount){
                    mode.add(root.val);
                }
            }
        }

        prev = root; //更新节点

        traverse(root.right);

    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/882460
推荐阅读
相关标签
  

闽ICP备14008679号