完全二叉樹 GO語言實(shí)現(xiàn)

完全二叉樹和滿二叉樹也有很好的性質(zhì)娄周,有時候會利用它們的特點(diǎn)求解

完全二叉樹常用層次遍歷。畢竟是最后一層或者次一層才會有葉子節(jié)點(diǎn)

662.?Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a?full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the?null?nodes between the end-nodes are also counted into the length calculation.

求樹的寬度,開始想用層次遍歷洛勉,如果打印出每一行页屠,然后遍歷每一行,就可以選出最寬的特幔。

但是發(fā)現(xiàn)咨演,這種方案會忽略空節(jié)點(diǎn),而有些時候空節(jié)點(diǎn)是可以占位

于是就想補(bǔ)全空節(jié)點(diǎn)蚯斯,但是補(bǔ)全空節(jié)點(diǎn)雪标,只有當(dāng)父親不為空的時候,才方便補(bǔ)空的孩子溉跃,但是當(dāng)父親為空村刨,也有可能需要孩子占位,比如[1,1,1,null,null,1,1,null,null,1]撰茎,而且此時復(fù)雜度就比較高了

好的方法可以是嵌牺,其實(shí)就是想補(bǔ)成滿二叉樹,但是還要知道哪些是原來的,哪些是補(bǔ)的逆粹。也就是說募疮,要是能直接知道當(dāng)前節(jié)點(diǎn)的位置就好了。其實(shí)可以的僻弹,由根節(jié)點(diǎn)開始阿浓,每個節(jié)點(diǎn)的位置,在滿二叉樹中蹋绽,就是父節(jié)點(diǎn)的二倍芭毙,或者兩倍加1,這樣每個節(jié)點(diǎn)的位置都知道卸耘,然后就是選出同一層的退敦,求最值

求最值可以再遍歷過程中只保持最大的


注意,只在隊(duì)列中保存非空節(jié)點(diǎn)蚣抗,效率更高

要習(xí)慣和敢于用更多的數(shù)據(jù)結(jié)構(gòu)緩存以解決問題和提升效率

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末侈百,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子翰铡,更是在濱河造成了極大的恐慌钝域,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,639評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件锭魔,死亡現(xiàn)場離奇詭異网梢,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)赂毯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評論 3 385
  • 文/潘曉璐 我一進(jìn)店門战虏,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人党涕,你說我怎么就攤上這事烦感。” “怎么了膛堤?”我有些...
    開封第一講書人閱讀 157,221評論 0 348
  • 文/不壞的土叔 我叫張陵透揣,是天一觀的道長屠凶。 經(jīng)常有香客問我,道長,這世上最難降的妖魔是什么橄碾? 我笑而不...
    開封第一講書人閱讀 56,474評論 1 283
  • 正文 為了忘掉前任饮醇,我火速辦了婚禮低千,結(jié)果婚禮上掺栅,老公的妹妹穿的比我還像新娘。我一直安慰自己誉帅,他們只是感情好淀散,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,570評論 6 386
  • 文/花漫 我一把揭開白布右莱。 她就那樣靜靜地躺著,像睡著了一般档插。 火紅的嫁衣襯著肌膚如雪慢蜓。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,816評論 1 290
  • 那天郭膛,我揣著相機(jī)與錄音晨抡,去河邊找鬼。 笑死则剃,一個胖子當(dāng)著我的面吹牛耘柱,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播忍级,決...
    沈念sama閱讀 38,957評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼伪朽!你這毒婦竟也來了轴咱?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,718評論 0 266
  • 序言:老撾萬榮一對情侶失蹤烈涮,失蹤者是張志新(化名)和其女友劉穎朴肺,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體坚洽,經(jīng)...
    沈念sama閱讀 44,176評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡戈稿,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,511評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了讶舰。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片鞍盗。...
    茶點(diǎn)故事閱讀 38,646評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖跳昼,靈堂內(nèi)的尸體忽然破棺而出般甲,到底是詐尸還是另有隱情,我是刑警寧澤鹅颊,帶...
    沈念sama閱讀 34,322評論 4 330
  • 正文 年R本政府宣布敷存,位于F島的核電站,受9級特大地震影響堪伍,放射性物質(zhì)發(fā)生泄漏锚烦。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,934評論 3 313
  • 文/蒙蒙 一帝雇、第九天 我趴在偏房一處隱蔽的房頂上張望涮俄。 院中可真熱鬧,春花似錦尸闸、人聲如沸禽拔。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽睹栖。三九已至硫惕,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間野来,已是汗流浹背恼除。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留曼氛,地道東北人豁辉。 一個月前我還...
    沈念sama閱讀 46,358評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像舀患,于是被迫代替她去往敵國和親徽级。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,514評論 2 348

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