二叉樹的周游算法
- 前序遍歷：visit（node），preorder(left Subtree)， preorder(right Subtree)。
- 中序遍歷：in-order(left Subtree)强品，visit（node），in-order(right Subtree)屈糊。
- 后序遍歷：post-order(left Subtree)的榛，post-order(right Subtree)，visit（node）逻锐。
- 層級(jí)遍歷：一層層訪問每個(gè)節(jié)點(diǎn)夫晌。
通過(guò)上述四種方式遍歷二叉樹的每個(gè)節(jié)點(diǎn)。
練習(xí)周游算法的技巧 1
思路：一般我們習(xí)慣 昧诱，根節(jié)點(diǎn)-左節(jié)點(diǎn)-右節(jié)點(diǎn)晓淀，這樣的模型，我們就把例如上圖A的左子樹當(dāng)做一個(gè)塊盏档，類似一個(gè)大節(jié)點(diǎn)用括號(hào)圈起來(lái)凶掰，同樣的右子樹也這樣做。然后每個(gè)塊里做前中后遍歷。
前序遍歷懦窘。A前翎，（B，D奶赠，E）鱼填，（C，F(xiàn)毅戈，G）。得到結(jié)果是 A愤惰，B苇经，D，E宦言，C扇单，F(xiàn)，G 奠旺。
中序遍歷蜘澜。（D，B响疚，E）鄙信，A，（F忿晕，C装诡，G）。得到的結(jié)果是 D践盼，B鸦采，E，A咕幻，F(xiàn)渔伯，C，G 肄程。
后序遍歷锣吼。（D，E绷耍，B）吐限，（F，G褂始，C）诸典，A。得到的結(jié)果是 D，E狐粱，B舀寓，F(xiàn)，G肌蜻，C互墓，A 。
層級(jí)遍歷蒋搜。 A篡撵，B，C豆挽，D育谬，E，F(xiàn)帮哈，G 膛檀。
練習(xí)周游算法的技巧 2
前序遍歷思路：每個(gè)節(jié)點(diǎn)從左邊畫線一直到底部這個(gè)線，然后按照從左到右的順序讀取節(jié)點(diǎn)娘侍。
結(jié)果是：A咖刃，B，D憾筏，E嚎杨，C，F(xiàn)踩叭，G 磕潮。
中序遍歷思路：每個(gè)節(jié)點(diǎn)從中間畫線到底部這個(gè)線，然后按照從左到右的順序讀取節(jié)點(diǎn)容贝。
結(jié)果是 D自脯，B，E斤富，A膏潮，F(xiàn)，C满力，G 焕参。
后序遍歷思路：每個(gè)節(jié)點(diǎn)從右邊畫線到底部這條線，然后從左到右的順序讀取節(jié)點(diǎn)油额。
結(jié)果是 D叠纷，E，B潦嘶，F(xiàn)涩嚣，G，C，A 航厚。
練習(xí)周游算法的技巧 3
前序遍歷思路：從每個(gè)節(jié)點(diǎn)左邊畫出一個(gè)線顷歌，然后從根結(jié)點(diǎn)開始轉(zhuǎn)一圈，經(jīng)過(guò)每個(gè)節(jié)點(diǎn)和樹的分支幔睬，包裹這個(gè)樹眯漩。經(jīng)過(guò)這些短線的順序就是結(jié)果。A麻顶，B赦抖，D，E辅肾，C摹芙，F(xiàn)，G 宛瞄。
中序遍歷思路：從每個(gè)節(jié)點(diǎn)底部邊畫出一個(gè)線，然后從根結(jié)點(diǎn)開始轉(zhuǎn)一圈交胚，經(jīng)過(guò)每個(gè)節(jié)點(diǎn)和樹的分支份汗，包裹這個(gè)樹。經(jīng)過(guò)這些短線的順序就是結(jié)果蝴簇。D杯活，B，E熬词，A旁钧，F(xiàn)，C互拾，G 歪今。
后序遍歷思路：從每個(gè)節(jié)點(diǎn)右邊畫出一個(gè)線，然后從根結(jié)點(diǎn)開始轉(zhuǎn)一圈颜矿，經(jīng)過(guò)每個(gè)節(jié)點(diǎn)和樹的分支寄猩，包裹這個(gè)樹。經(jīng)過(guò)這些短線的順序就是結(jié)果骑疆。D田篇，E，B慌申，F(xiàn)兵志，G仅醇，C，A 兽赁。
延伸
- 前序遍歷，中序遍歷，后續(xù)遍歷的思想是按照深度優(yōu)先的順序遍歷的闸氮。層級(jí)遍歷的思想是按照廣度優(yōu)先的順序遍歷的剪况。
- 由于要遍歷樹的每個(gè)節(jié)點(diǎn)因此時(shí)間復(fù)雜度是O（n）。
- 廣度優(yōu)先遍歷思想的層級(jí)遍歷需要的額外的空間是O（w）,w是這個(gè)二叉樹的最大的寬蒲跨，比如Perfect Binary Tree這種情況下最大節(jié)點(diǎn)在最后一層译断，第i層至多擁有2i-1個(gè)節(jié)點(diǎn)，因此需要額外空間O（Ceil(n/2)）或悲；深度優(yōu)先遍歷思想的其他三種方式需要額外空間是O（h）,這個(gè)h是二叉樹的最大高度孙咪，比如一個(gè)平衡樹h是Log2(n) ,但是對(duì)于極不平衡的左傾斜或者右傾斜樹來(lái)說(shuō)h就是n 。所以在最壞的情況下巡语，兩者所需的額外空間是O（n）翎蹈。但最壞的情況發(fā)生在不同類型的樹木上，因此針對(duì)不同種類不同性質(zhì)的樹需要的額外空間有不盡相同男公。從以上可以明顯看出荤堪，當(dāng)樹更平衡時(shí)，廣度優(yōu)先遍歷思想的層級(jí)遍歷所需的額外空間可能更多枢赔，并且當(dāng)樹不太平衡時(shí)澄阳，深度優(yōu)先遍歷思想的其他三種遍歷方式的額外空間可能更多。
Github
https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm
