Star

LeetCode 501. Find Mode in Binary Search Tree

Posted on |

Question

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

Explanation

递归，注意要用全局变量保存之前的最大值，还有当前值。中序遍历整棵树，保存当前的值和count，如果和前面的值不同了，就重新计数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    List<Integer> list;
    int max;
    int currval;
    int currcount;
    public int[] findMode(TreeNode root) {
        if(root == null) return new int[0];
        currval =0;
        currcount = 0;
        helper(root);
        int[] res = new int[list.size()];
        for(int i = 0; i<res.length; i++) res[i] = list.get(i);
        return res;
    }
    public void helper(TreeNode root) {
        if (root == null) return;
        helper(root.left);
        if(root.val == currval) {
            currcount ++;
        } else {
            currcount = 1;
            currval = root.val;
        }
        if (currcount > max) {
            max = currcount;
            list = new ArrayList<>();
            list.add(root.val);
        } else if(currcount == max) {
            list.add(root.val);
        }
        helper(root.right);
    }
}