501. Find Mode in Binary Search Tree

Problem:

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Analysis:

按inorder走，然后count 每个数出现的次数，如果count > max，更新结果。count == max， 加入到result list中。

Solution:

class Solution {
    TreeNode pre;
    int count = 1;
    int max = 0;
    public int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null)
            return;
        inorder(node.left, list);
        if (pre != null) {
            count = (node.val == pre.val) ? count + 1 : 1;
        }

        if (count >= max) {
            if (count > max) list.clear();
            list.add(node.val);
            max = count;
        }
        pre = node;
        inorder(node.right, list);
    }
}