leetcode 501. 二叉搜索树中的众数（Java版）

偏执的太偏执、 2023-01-19 04:40 138阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/][https_leetcode-cn.com_problems_find-mode-in-binary-search-tree]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

中序遍历二叉搜索树，可以得到一个有序序列。

遍历这个有序序列，找到众数。

import java.util.*;
    
    class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode() { 
        }
    
        TreeNode(int val) { 
            this.val = val;
        }
    
        TreeNode(int val, TreeNode left, TreeNode right) { 
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public class Solution { 
        public int[] findMode(TreeNode root) { 
            // 中序遍历得到有序序列
            ArrayList<Integer> list = new ArrayList<>();
            inOrder(root, list);
    
            // list 转 array
            int[] sortedArray = new int[list.size()];
            for (int i = 0; i < list.size(); i++) { 
                sortedArray[i] = list.get(i);
            }
    
            // 找到众数（可能包含多个）
            int base = sortedArray[0];
            int count = 1;
            int maxCount = 1;
            ArrayList<Integer> answer = new ArrayList<>();
            answer.add(sortedArray[0]);
            for (int i = 1; i < sortedArray.length; i++) { 
                if (sortedArray[i] == base) { 
                    ++count;
                } else { 
                    count = 1;
                    base = sortedArray[i];
                }
                if (count == maxCount) { 
                    answer.add(base);
                }
                if (count > maxCount) { 
                    maxCount = count;
                    answer.clear();
                    answer.add(base);
                }
            }
    
            int[] arr = new int[answer.size()];
            for (int i = 0; i < answer.size(); i++) { 
                arr[i] = answer.get(i);
            }
            return arr;
        }
    
        public void inOrder(TreeNode node, List<Integer> list) { 
            if (node == null) return;
            inOrder(node.left, list);
            list.add(node.val);
            inOrder(node.right, list);
        }
    
        // for test
        public static void main(String[] args) { 
            TreeNode t1 = new TreeNode(1);
            TreeNode t2_1 = new TreeNode(2);
            TreeNode t2_2 = new TreeNode(2);
            t1.right = t2_1;
            t2_1.left = t2_2;
    
            int[] arr = new Solution().findMode(t1);
            for (int i = 0; i < arr.length; i++) { 
                System.out.println(arr[i]);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_find-mode-in-binary-search-tree]: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221021/5bdb0092a2f4487690ba8d133e8b0be2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221021/c6b3bb0779fd4cbdaf4c5caa282c1b4f.png