題目連結:
題目意譯:
給定一棵可重複元素的二元搜尋樹(Binary Search Tree,BST),找到 BST 中所有的眾數(出現最多次的元素)。
假設一棵 BST 定義如下:
一個節點的左子樹只包含擁有小於或等於此節點鍵值(Key)的鍵值之節點。
一個節點的右子樹只包含擁有大於或等於此節點鍵值(Key)的鍵值之節點。
左子樹以及右子樹都同樣是二元搜尋樹。
注:如果一個樹有多個眾數,則可以任意順序將它們回傳。
進階:你可以不使用額外的記憶體空間嗎?(假設遞迴隱含的堆疊空間所占的記憶體空間不算)
範例測資:
給定 BST 為 [1,null,2,2],
1
\
2
/
2
回傳 [2]。
解題思維:
二元搜尋樹有一個特性——其中序探訪(
這題有說明中序探訪的意思)得到的序列為一個已排序好的數列。
因此,我們就對該樹做中序探訪。由上特性可知此行為等價於掃過一個排序好的數字陣列,因此眾數就變成了連續出現最多次的數字(因為相同的數字會排在一起),如
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。