[LeetCode] 501. Find Mode in Binary Search Tree

轉自LeetCode

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

<Solution>

想法如下

• 用任何 binary tree traversal 的方式歷遍一次，算出最多的出現次數，同時也用 hashmap 記錄每個數字出現的次數。這邊因為想要讓空間複雜度為 O(1)，所以使用 Morris Traversal (inorder)

• 找出最多次數後，把 hashmap 裡面出現次數等於最多次數的數字，放到答案裡就可以了

code 如下

C++

Java

kotlin