Easy

501. Find Mode in Binary Search Tree

treedepth-first-searchbinary-search-treebinary-tree

解題說明

Find Mode in Binary Search Tree

題目描述：給定一棵含有重複值的二元搜尋樹（BST），找出所有出現頻率最高的元素（眾數）。

解題思路：BST 的中序遍歷結果是非遞減序列，相同的值必然相鄰。利用此性質，只需一次中序遍歷並維護一個 prev 指標，即可追蹤當前值的連續出現次數。當計數超過全域最大頻率時，清空結果並更新；若等於最大頻率則加入結果。使用 Morris Traversal 可在 O(1) 額外空間下完成。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點在 Morris Traversal 中最多被訪問兩次。

空間複雜度：O(1) — 不計輸出陣列，Morris Traversal 不使用額外空間（遞迴堆疊或顯式堆疊）。

虛擬碼

1. Initialize result = [], maxCount = 0, curCount = 0, curVal = 0, prev = null
2. Morris inorder traversal on root:
   a. For each visited node:
      - If node.val == curVal: curCount++
      - Else: curVal = node.val, curCount = 1
      - If curCount > maxCount: maxCount = curCount, clear result, add curVal
      - Else if curCount == maxCount: add curVal to result
3. Return result

其他解法

雜湊表計數 O(n) 空間：普通 DFS 遍歷，用雜湊表記錄每個值的出現次數，再找最大值。適用於任意二元樹（不僅限 BST），但需 O(n) 額外空間。

兩次遍歷法 O(1) 空間：第一次遍歷找出最大頻率 maxCount，第二次遍歷收集所有頻率等於 maxCount 的值。兩次中序遍歷各 O(n)，不需要動態陣列清空操作。

延伸思考

如果 BST 中沒有重複值，眾數是什麼？此時的答案有何特點？
若輸入不是 BST 而是普通二元樹，還能在 O(1) 額外空間下解決嗎？
如何修改算法以找出第 k 大頻率的元素？

Find Mode in Binary Search Tree — CaffeCode