501 Find Mode in Binary Search Tree

501. Find Mode in Binary Search Tree

1. Question

Given a binary search tree (BST) with duplicates, find all themode(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).

2. Implementation

(1) BFS + HashMap

class Solution {
    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        Map<Integer, Integer> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int max = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                map.put(curNode.val, map.getOrDefault(curNode.val, 0) + 1);
                max = Math.max(max, map.get(curNode.val));

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int key : map.keySet()) {
            if (max == map.get(key)) {
                list.add(key);
            }
        }

        int index = 0;
        int[] res = new int[list.size()];

        for (int e : list) {
            res[index++] = e;
        }
        return res;
    }
}

(2) Inorder Traversal

维护三个变量pre，curMax, max, pre指的是之前遍历到的value，curMax代表当前value的次数，max代表遇到的数中，出现最多的次数。利用Binary Search Tree的特点，对树进行中序遍历。因为是有序的，所以我们可以通过之前遍历到的value和当前的value作比较，如果相同，则curMax加1，否则将它更新为1. 而如果curMax和max相同时，则modes这个数列加上当前的node value，如果curMax > max时，则要更新max的值，并更新modes数列，让它只包含当前的node value。中序遍历结束后，我们要的mode都在modes这个数列里

class Solution {
    public int[] findMode(TreeNode root) {
        int[] pre = new int[1];
        int[] curMax = new int[1];
        int[] max = new int[1];
        List<Integer> modes = new ArrayList<>();

        inorderTraverse(root, pre, curMax, max, modes);

        int[] res = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            res[i] = modes.get(i);
        }
        return res;
    }

    public void inorderTraverse(TreeNode node, int[] pre, int[] curMax, int[] max, List<Integer> modes) {
        if (node == null) {
            return;
        }

        inorderTraverse(node.left, pre, curMax, max, modes);

        if (node.val == pre[0]) {
            curMax[0] += 1;
        }
        else {
            curMax[0] = 1;
        }

        if (curMax[0] == max[0]) {
            modes.add(node.val);
        }
        else if (curMax[0] > max[0]) {
            max[0] = curMax[0];
            modes.clear();
            modes.add(node.val);
        }

        pre[0] = node.val;

        inorderTraverse(node.right, pre, curMax, max, modes);
    }
}

3. Time & Space Complexity

BFS + HashMap: 时间复杂度:O(n), 空间复杂度: O(n)

Inorder Traversal: 时间复杂度: O(n), 空间复杂度: O(n)