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

找眾數(shù)

用use HashMap<Integer, frequency>

(List??)
返回int[]
traverse: inorder, pre, post - anyone is fine

O(n)時間復(fù)雜度

R:
Java:Map與HashMap套腹,Hashtable电禀,HashSet比較

  • List in Java

有序笤休、可重復(fù); 可以持續(xù)擴展大小(array不可以)
ListList集合代表一個元素有序葫松、可重復(fù)的集合腋么,集合中每個元素都有其對應(yīng)的順序索引珊擂。注意: List集合默認(rèn)按元素的添加順序設(shè)置元素索引费变,例如第 ...

==> 用List的原因是:List可以持續(xù)擴展大小,而且數(shù)組不可以挚歧。

Java數(shù)組聲明后其長度就固定了滑负,不能增加長度用含。 要創(chuàng)建一個可擴展的數(shù)組可以使用ArrayList或Vector啄骇。

class Solution {
    HashMap<Integer, Integer> map;
        // = new HashMap<>();
    int max = 0; 
    
    public int[] findMode(TreeNode root) {
        if(root == null) {return new int[0];}
        this.map = new HashMap<>();
        
        inorder(root);
        
        List<Integer> list = new LinkedList<>();
        for(int key: map.keySet()) {
            if(map.get(key) == max) {list.add(key);}
        }
        
        int[] res = new int[list.size()];
        for(int i = 0; i<res.length; i++) res[i] = list.get(i);
        // transfer the LinkedList list to int[] res
        
        return res;
    }
    
    private void inorder(TreeNode node) {
        if(node.left != null) {inorder(node.left);}
        map.put(node.val, map.getOrDefault(node.val, 0) + 1);
        max = Math.max(max, map.get(node.val));
        // constantly update the maximum node.val
        if(node.right != null) {inorder(node.right);}
    }
}

評價:
O(n) Time, O(n) Space;
it doesn't use the property of BST.

// P?NP?PSPACE=NPSPACE?EXPTIME

O(1) Space

public class Solution {
    
    public int[] findMode(TreeNode root) {
        inorder(root);
        modes = new int[modeCount];
        modeCount = 0;
        currCount = 0;
        inorder(root);
        return modes;
    }

    private int currVal;
    private int currCount = 0;
    private int maxCount = 0;
    private int modeCount = 0;
    
    private int[] modes;

    private void handleValue(int val) {
        if (val != currVal) {
            currVal = val;
            currCount = 0;
        }
        currCount++;
        if (currCount > maxCount) {
            maxCount = currCount;
            modeCount = 1; // BSTinorder遍歷時缸夹,單調(diào)遞增的屬性
        } else if (currCount == maxCount) {
            if (modes != null)
                modes[modeCount] = currVal;
            modeCount++;
        }
    }
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        handleValue(root.val);
        inorder(root.right);
    }
}

遍歷了兩遍螺句,但是只用了一個modes[]壹蔓,只占用O(1)Space。
第一遍找到眾數(shù)with highest frequency佣蓉,并且記為N勇凭;
第二遍將所有出現(xiàn)了N次的數(shù)組都存在一個modes里。

I think the way to do it properly is to do two passes.

每次遍歷一個數(shù)字Val時:
currVal = Val, 記錄當(dāng)前數(shù)字出現(xiàn)的次數(shù)currCount寓盗;

對得到對currCount進行判斷:
是否出現(xiàn)次數(shù)大于maxCount傀蚌,是則 - 1. 更新最大頻率maxCount蘸吓,2. 新的maxCount 對應(yīng)的數(shù)字個數(shù) 更新為1(后期出現(xiàn)頻率相同的數(shù)字時modeCount++)。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末箩艺,一起剝皮案震驚了整個濱河市宪萄,隨后出現(xiàn)的幾起案子拜英,更是在濱河造成了極大的恐慌,老刑警劉巖撒妈,帶你破解...
    沈念sama閱讀 217,277評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件狰右,死亡現(xiàn)場離奇詭異舆床,居然都是意外死亡挨队,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評論 3 393
  • 文/潘曉璐 我一進店門湿弦,熙熙樓的掌柜王于貴愁眉苦臉地迎上來颊埃,“玉大人蝶俱,你說我怎么就攤上這事÷薇辏” “怎么了闯割?”我有些...
    開封第一講書人閱讀 163,624評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長纽谒。 經(jīng)常有香客問我鼓黔,道長不见,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,356評論 1 293
  • 正文 為了忘掉前任缎谷,我火速辦了婚禮列林,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘希痴。我一直安慰自己砌创,他們只是感情好嫩实,可當(dāng)我...
    茶點故事閱讀 67,402評論 6 392
  • 文/花漫 我一把揭開白布甲献。 她就那樣靜靜地躺著宰缤,像睡著了一般。 火紅的嫁衣襯著肌膚如雪晃洒。 梳的紋絲不亂的頭發(fā)上慨灭,一...
    開封第一講書人閱讀 51,292評論 1 301
  • 那天,我揣著相機與錄音锥累,去河邊找鬼缘挑。 笑死,一個胖子當(dāng)著我的面吹牛桶略,可吹牛的內(nèi)容都是我干的语淘。 我是一名探鬼主播,決...
    沈念sama閱讀 40,135評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼际歼,長吁一口氣:“原來是場噩夢啊……” “哼惶翻!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起鹅心,我...
    開封第一講書人閱讀 38,992評論 0 275
  • 序言:老撾萬榮一對情侶失蹤吕粗,失蹤者是張志新(化名)和其女友劉穎颅筋,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體先口,經(jīng)...
    沈念sama閱讀 45,429評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,636評論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了夹纫。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片舰讹。...
    茶點故事閱讀 39,785評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖素标,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情计维,我是刑警寧澤鲫惶,帶...
    沈念sama閱讀 35,492評論 5 345
  • 正文 年R本政府宣布赏淌,位于F島的核電站,受9級特大地震影響缩擂,放射性物質(zhì)發(fā)生泄漏懈费。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,092評論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望阵谚。 院中可真熱鬧梢什,春花似錦、人聲如沸荔睹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至峡蟋,卻和暖如春仅乓,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背豫喧。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評論 1 269
  • 我被黑心中介騙來泰國打工鸟妙, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個月前我還...
    沈念sama閱讀 47,891評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,713評論 2 354

推薦閱讀更多精彩內(nèi)容