501. Find Mode in Binary Search Tree

女爷i 2021-11-29 18:42 196阅读 0赞

Given a binary search tree (BST) with duplicates, find all the [mode(s)][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).

private readonly Dictionary<int, int> dictionary = new Dictionary<int, int>();
    
            public int[] FindMode(TreeNode root)
            {
                Chuck(root);
                if (dictionary.Count > 0)
                {
                    int max = dictionary.Max(x => x.Value);
                    var array = dictionary.Where(x => x.Value == max).Select(x => x.Key).ToArray();
                    return array;
                }
                else
                {
                    return new int[0];
                }
            }
    
            private void Chuck(TreeNode node)
            {
                if (node == null)
                {
                    return;
                }
    
                int val = node.val;
                if (dictionary.ContainsKey(val))
                {
                    dictionary[val]++;
                }
                else
                {
                    dictionary[val] = 1;
                }
                Chuck(node.left);
                Chuck(node.right);
            }

Runtime:  272 ms, faster than 32.05% of C\# online submissions for Find Mode in Binary Search Tree.

Memory Usage:  33.1 MB, less than 11.30% of C\# online submissions forFind Mode in Binary Search Tree.

转载于:https://www.cnblogs.com/chucklu/p/10959760.html

[mode_s]: https://en.wikipedia.org/wiki/Mode_%28statistics%29