# Find Mode in Binary Search Tree

Leave a commentJune 21, 2017 by oneOokay

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

如果用hashmap的话是很简单,但是一个without using any extra space的解法挺有意思的. O(1).

我自己要注意的点就是:尽管这个是允许duplicates的 binary search tree,在树上看相同的值可能到处是,但是只要inorder traversal的输出,数字的大小就是按照顺序排列的.

O(1)的用了两次inorder traversal: 第一次得到modes的个数,然后新建那个int[] array.第二次inorder traversal fill in result array

public int[] findMode(TreeNode root) { inorder(root); modesRes = new int[modeCount]; modeCount = 0;//reset modeCount; curCount = 0; //reset curCount; inorder(root); return modesRes; } private int currVal; private int curCount = 0; private int maxCount = 0; private int modeCount = 0; private int[] modesRes; private void handleValue(int value){ if (value != currVal){ currVal = value; curCount = 0; } curCount ++; if (curCount > maxCount){ maxCount = curCount; modeCount = 1; //reset mode count }else if (curCount == maxCount){ if (modesRes != null){ modesRes[modeCount] = currVal; } modeCount ++; } } private void inorder(TreeNode node){ if (node == null) return; inorder(node.left); handleValue(node.val); inorder(node.right); }

Advertisements