完全二叉樹和滿二叉樹也有很好的性質(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)緩存以解決問題和提升效率