赞
踩
解题思路:
二叉搜索树,考虑中序遍历,此题类似有序遍历数组。
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); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。