[bst] 501. Find Mode in Binary Search Tree

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).

首先想到最原始的方法,并不需要利用bst的特点,直接遍历,然后存map记录每个node的个数,记住mode(即最大的)count是多少,再从map中找到所有符合mode count的node

    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap();
        int max = helper(root, map, 0);
        List<Integer> list = new ArrayList();
        for (int val : map.keySet()) {
            if (map.get(val) == max) {
                list.add(val);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        
        return res;
    }
    
    private int helper(TreeNode root, Map<Integer, Integer> map, int max) {
        if (root == null) return max;
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        max = Math.max(max, map.get(root.val));
        if (root.left != null) {
            int lmax = helper(root.left, map, max);
            max = Math.max(max, lmax);
        }
        
        if (root.right != null) {
            int rmax = helper(root.right, map, max);
            max = Math.max(max, rmax);
        }
        
        return max;
    }

比较啰嗦,运行速度慢,还需要extra space

因为follow up中要求不能使用extra space。想到bst是可以按大小顺序遍历tree的,如果需要排序,则需要inorder遍历。这样遍历一遍就可以知道mode的count是多少,有几个。再遍历第二遍,找到符合mode count的node即可。

    int curval = 0;
    int curcount = 0;
    int[] mode;
    int maxcount = 0;
    int modecount = 0;
    public int[] findMode(TreeNode root) {
        first(root);
        mode = new int[modecount];
        curcount = 0;
        modecount = 0;
        second(root);
        return mode;
    }
    
    private void first(TreeNode root) {
        if (root == null) return;
        first(root.left);
        
        // handle value
        int val = root.val;
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        if (curcount > maxcount) {
            maxcount = curcount;
            modecount = 1;
        } else if (curcount == maxcount) {
            modecount++;
        }
        first(root.right);
        
    }
    
    private void second(TreeNode root) {
        if (root == null) return;
        second(root.left);
        
        // handle value
        int val = root.val;
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        
        if (curcount == maxcount) {
            mode[modecount] = curval;
            modecount++;
        }
        
        second(root.right);
    }

space,time complexity都提高了,code很啰嗦,再improve一下,发现两个pass的handle value部分都差不多,合并成一个

    int curval = 0;
    int curcount = 0;
    int[] mode;
    int maxcount = 0;
    int modecount = 0;
    public int[] findMode(TreeNode root) {
        inorder(root);
        mode = new int[modecount];
        curcount = 0;
        modecount = 0;
        inorder(root);
        return mode;
    }
    
    private void handleval(int val) {
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        if (curcount > maxcount) {
            maxcount = curcount;
            modecount = 1;
        } else if (curcount == maxcount) {
            if (mode != null) {
                mode[modecount] = curval;
            }
            modecount++;
        }
    }
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        handleval(root.val);
        inorder(root.right);
    }