前往
大廳
主題

LeetCode - 501. Find Mode in Binary Search Tree 解題心得

Not In My Back Yard | 2020-11-05 00:00:04 | 巴幣 100 | 人氣 411

題目連結:


題目意譯:
給定一棵可重複元素的二元搜尋樹(Binary Search Tree,BST),找到 BST 中所有的眾數(出現最多次的元素)。

假設一棵 BST 定義如下:
一個節點的左子樹只包含擁有小於或等於此節點鍵值(Key)的鍵值之節點。
一個節點的右子樹只包含擁有大於或等於此節點鍵值(Key)的鍵值之節點。
左子樹以及右子樹都同樣是二元搜尋樹。

注:如果一個樹有多個眾數,則可以任意順序將它們回傳。

進階:你可以不使用額外的記憶體空間嗎?(假設遞迴隱含的堆疊空間所占的記憶體空間不算)



範例測資:
給定 BST 為 [1,null,2,2],
 \
  2
 /
回傳 [2]。


解題思維:
二元搜尋樹有一個特性——其中序探訪(這題有說明中序探訪的意思)得到的序列為一個已排序好的數列。

因此,我們就對該樹做中序探訪。由上特性可知此行為等價於掃過一個排序好的數字陣列,因此眾數就變成了連續出現最多次的數字(因為相同的數字會排在一起),如這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作