Skip to content

Latest commit

 

History

History
55 lines (35 loc) · 2.17 KB

0501-find-mode-in-binary-search-tree.adoc

File metadata and controls

55 lines (35 loc) · 2.17 KB

501. Find Mode in Binary Search Tree

{leetcode}/problems/find-mode-in-binary-search-tree/[LeetCode - 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).

思路分析

看到二叉搜索树，应该条件反射般想到二叉搜索树的中根遍历是有序的。

由于中根遍历有序的特性，那么相同的数字就会一起出现，在出现的时候，统计每个数字出现的次数即可。思想容易理解，重点是代码的实现。有两个地方可以稍微简化一下代码：

  • 先更新要处理的数字及次数；

  • 然后根据次数，就可以处理需要的结果。

link:{sourcedir}/_0501_FindModeInBinarySearchTree.java[role=include]