每日一道LeetCode——二叉搜索树中的众数

题目： 我的解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
          
   
    List<Integer> list = new ArrayList<Integer>();
    public int[] findMode(TreeNode root) {
          
   
        if (root==null){
          
   
            return new int[0];
        }
        List<Integer> temp = new ArrayList<Integer>();
        // 将搜索二叉树转化为list
        addToList(root);
        int max_freq = 0;
        int cur_freq = 0;
        int pre_Val = 0;

        for(int i=0; i<=list.size(); i++){
          
   
        // 处理第一个元素
           if(i==0){
          
   
               pre_Val = list.get(i);
               max_freq = 1;
               cur_freq = 1;
           }else if (i==list.size()){
          
   
           // 处理最后一个元素
               if(cur_freq>max_freq){
          
   
                    max_freq = cur_freq;
                    temp.clear();
                    temp.add(list.get(i-1));
                }else if(cur_freq==max_freq){
          
   
                    temp.add(list.get(i-1));
                }
           }else{
          
   
           // 如果当前元素与上一元素相等，当前计数加1
               if (list.get(i)==pre_Val){
          
   
                   cur_freq += 1;
               }else{
          
   
              	// 如果不相等，判断当前计数与最大计数
                   if(cur_freq>max_freq){
          
   
                       max_freq = cur_freq;
                       temp.clear();
                       temp.add(list.get(i-1));
                   }else if(cur_freq==max_freq){
          
   
                        temp.add(list.get(i-1));
                   }
                   cur_freq = 1;
               }
               pre_Val = list.get(i);
           }
        }
        int[] result = new int[temp.size()];
        for(int i=0; i<temp.size(); i++){
          
   
            result[i] = temp.get(i);
        }
        return result;
    }

    public void addToList(TreeNode t){
          
   
        if (t.left!=null){
          
   
            addToList(t.left);
        }
        if (t!=null){
          
   
            list.add(t.val);
        }
        if (t.right!=null){
          
   
            addToList(t.right);
        }
    }
}

官方题解：

class Solution {
          
   
    int base, count, maxCount;
    List<Integer> answer = new ArrayList<Integer>();

    public int[] findMode(TreeNode root) {
          
   
        TreeNode cur = root, pre = null;
        while (cur != null) {
          
   
            if (cur.left == null) {
          
   
                update(cur.val);
                cur = cur.right;
                continue;
            }
            pre = cur.left;
            while (pre.right != null && pre.right != cur) {
          
   
                pre = pre.right;
            }
            if (pre.right == null) {
          
   
                pre.right = cur;
                cur = cur.left;
            } else {
          
   
                pre.right = null;
                update(cur.val);
                cur = cur.right;
            }
        }
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
          
   
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void update(int x) {
          
   
        if (x == base) {
          
   
            ++count;
        } else {
          
   
            count = 1;
            base = x;
        }
        if (count == maxCount) {
          
   
            answer.add(base);
        }
        if (count > maxCount) {
          
   
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }
}