上一篇文章介紹了鏈表猴誊，這篇文章繼續(xù)分享算法心得阁将，即另一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)——樹膏秫。
樹的特點(diǎn)
樹和鏈表相對(duì)比，會(huì)更加復(fù)雜一些做盅。實(shí)際上鏈表中節(jié)點(diǎn)有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)缤削，而在樹中窘哈，有兩個(gè)指針，分別指向左亭敢，右兩個(gè)孩子節(jié)點(diǎn)滚婉。這種對(duì)應(yīng)關(guān)系，就不是鏈表中的一對(duì)一了帅刀，在樹中让腹，對(duì)應(yīng)關(guān)系就是一對(duì)多了。如果說鏈表可以理解為一維的世界扣溺，則樹就是二維的世界了骇窍。特別的，樹這個(gè)二維世界有一個(gè)非常重要的節(jié)點(diǎn)就是根節(jié)點(diǎn)锥余，這個(gè)節(jié)點(diǎn)可以認(rèn)為是樹的特征節(jié)點(diǎn)腹纳。因此解決樹的問題，找準(zhǔn)根節(jié)點(diǎn)是非常重要哈恰。
在23種設(shè)計(jì)模式中只估，組合模式就是運(yùn)用了樹這種數(shù)據(jù)結(jié)構(gòu)志群。組合模式的意思就是操作樹根這一個(gè)元素着绷，好像同時(shí)操作整個(gè)樹一樣。在實(shí)際的應(yīng)用中锌云，樹可以理解為一種層級(jí)結(jié)構(gòu)荠医，比如界面，windows可能是樹根桑涎，樹根會(huì)有視圖彬向，視圖又可分為用戶自定義的各種視圖控件，整個(gè)的ui界面攻冷，可以理解為一棵完整的樹娃胆，而操作樹根，比如windows接收到了點(diǎn)擊事件等曼，就可以將這個(gè)事件分發(fā)給這課樹的所有節(jié)點(diǎn)里烦。這就是組合模式。
樹的一個(gè)重要的特點(diǎn)禁谦，就是有一定的遞歸性胁黑，因此，在解決樹相關(guān)的問題時(shí)州泊，遞歸的方法丧蘸，顯然是首選。另外遥皂，結(jié)合樹中最重要的要點(diǎn)力喷，就是找到樹的特征也就是樹根刽漂。把握好這兩個(gè)方面，很多樹相關(guān)的問題就可以解決了弟孟。
樹的遍歷
樹既然具有二維性爽冕，一個(gè)重要的課題就是將二維轉(zhuǎn)換為一維，也就是樹的遍歷披蕉。樹的遍歷總共分為三種颈畸，前序遍歷，中序遍歷和后序遍歷没讲。這里的前眯娱，中和后都是說的根，也就是根遍歷的順序爬凑。實(shí)際上在樹的遍歷中徙缴，永遠(yuǎn)是先左節(jié)點(diǎn)，后右節(jié)點(diǎn)的嘁信。但是關(guān)鍵是根節(jié)點(diǎn)于样。如果先是根節(jié)點(diǎn)，然后左節(jié)點(diǎn)潘靖，最后右節(jié)點(diǎn)穿剖，就是前序遍歷，也就是根在前面遍歷卦溢。如果先是左節(jié)點(diǎn)糊余，然后根節(jié)點(diǎn)，最后右節(jié)點(diǎn)单寂，就是中序遍歷贬芥，也就是根在中間遍歷。如果先是左節(jié)點(diǎn)宣决，然后右節(jié)點(diǎn)蘸劈，最后根節(jié)點(diǎn)，就是后序遍歷尊沸，也就是根在最后遍歷威沫。
樹的三種遍歷方式，可以將二維的樹椒丧，轉(zhuǎn)換為一維的數(shù)組壹甥。前序，中序和后序是樹的一維形態(tài)壶熏。二維可以轉(zhuǎn)換為一維句柠，那么一維是否可以轉(zhuǎn)換為二維呢？這實(shí)際上就是一個(gè)面試題，我們將在下面詳細(xì)分析溯职。
樹的典型算法題
面試題7：重建二叉樹
題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果精盅，請(qǐng)重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字谜酒。
這是一道典型的由一維的遍歷重構(gòu)出二維的樹叹俏。由于不含重復(fù)的數(shù)字，因此這種重構(gòu)是可能的僻族≌吵郏可以這樣理解，用兩個(gè)一維數(shù)據(jù)述么，重構(gòu)出二維數(shù)據(jù)蝌数，這是可行的。題目要求用前序遍歷和中序遍歷重建二叉樹度秘，而樹的結(jié)構(gòu)顶伞，最重要的兩個(gè)元素就是根節(jié)點(diǎn)以及遞歸。一提到遞歸剑梳，我們就需要處理異常唆貌，終止以及問題化簡(jiǎn)。有了這些基本的武器后垢乙，我們看看如何解決這個(gè)問題锨咙。
解決樹的問題最核心的是找到根節(jié)點(diǎn)，如何找到根節(jié)點(diǎn)呢侨赡？很簡(jiǎn)單蓖租，前序遍歷中就有根節(jié)點(diǎn)了粱侣。前序遍歷之所以稱之為前序羊壹，就是因?yàn)槭鞘紫缺闅v根節(jié)點(diǎn)。因此齐婴，前序遍歷可以理解為 根節(jié)點(diǎn) + 左子樹節(jié)點(diǎn) + 右子樹節(jié)點(diǎn)油猫。如果我們想利用遞歸的思想，就必須對(duì)題目進(jìn)行簡(jiǎn)化柠偶，簡(jiǎn)化的方法就是將樹的問題轉(zhuǎn)換為左子樹和右子樹的問題情妖，這樣，就找到了問題的子問題诱担。這里我們根據(jù)前序遍歷的特點(diǎn)毡证，可以得到根節(jié)點(diǎn)，但是左子樹和右子樹的邊界我們是不清楚的蔫仙。因此料睛，想到利用另一個(gè)已知，即中序遍歷。中序遍歷的遍歷方式是 左子樹節(jié)點(diǎn) + 根節(jié)點(diǎn) + 右子樹節(jié)點(diǎn)恤煞。從前序遍歷中屎勘，我們已經(jīng)找到了根節(jié)點(diǎn)，因此從中序遍歷中就可以確定了根節(jié)點(diǎn)的位置居扒，根節(jié)點(diǎn)的左邊就是左子樹的中序遍歷概漱，根節(jié)點(diǎn)的右邊就是右子樹的中序遍歷。特別的喜喂，我們可以得到左子樹和右子樹的元素的個(gè)數(shù)瓤摧。確定了左子樹和右子樹元素的個(gè)數(shù)后，我們又可以通過前序遍歷玉吁，確定左子樹和右子樹的分割邊界姻灶。這樣，我們就可以得到左右子樹的前序遍歷诈茧。
分析到這里产喉，這個(gè)問題基本上就已經(jīng)解開了，我們成功的將問題轉(zhuǎn)換為子問題敢会，即我們可以分別得到根節(jié)點(diǎn)曾沈，以及左右子樹的前序和中序遍歷。通過遞歸鸥昏，我們就可以將這棵樹重建起來塞俱。
面試題32：從上到下打印二叉樹
題目：不分行從上到下打印二叉樹
從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印吏垮。
為什么想分享這樣一道面試題呢障涯？因?yàn)檫@道面試題，體現(xiàn)了樹這個(gè)數(shù)據(jù)結(jié)構(gòu)可以和其他一些數(shù)據(jù)結(jié)構(gòu)相組合膳汪。我們常用的數(shù)據(jù)結(jié)構(gòu)還有什么呢唯蝶？實(shí)際上還有先進(jìn)先出的隊(duì)列，以及先進(jìn)后出的棧遗嗽。有時(shí)粘我，解決樹相關(guān)的問題，也需要輔助隊(duì)列痹换，或者輔助棧征字，比如這道算法題就是一個(gè)典型。
這道題考察了一種特殊的樹的遍歷方式娇豫，這種方式既不是前序遍歷匙姜，也不是中序遍歷，更不是后序遍歷冯痢。而是一種自定義的遍歷方式氮昧，是按層級(jí)遍歷或详，也就是自上而下的遍歷。這種遍歷方式似乎破壞了樹的遞歸的特性郭计，那么我們有沒有什么好方法呢霸琴？
實(shí)際上這種遍歷方式，有些道家的一生二昭伸，二生三梧乘，三生萬物的意思了÷睿或者更形象些选调，就是太極生兩儀，兩儀生四象灵份，四象生八卦仁堪。這個(gè)太極，就是樹的根結(jié)構(gòu)填渠。既然有“生”弦聂，就要有容器去容納那些生出來的節(jié)點(diǎn)，由于這種“生”的方式氛什，符合先進(jìn)先出的特點(diǎn)莺葫，因此我們需要一個(gè)輔助隊(duì)列。首先我們把樹根扔進(jìn)這個(gè)隊(duì)列中枪眉，然后開始處理隊(duì)列捺檬。處理隊(duì)列的時(shí)候，我們首先將隊(duì)頭的那個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)扔進(jìn)隊(duì)列中贸铜，然后將這個(gè)節(jié)點(diǎn)彈出隊(duì)列堡纬，打印其信息。如此操作蒿秦，就是符合題目的遍歷方式了烤镐。
通過這個(gè)面試題，我們可以很清晰的看到渤早，樹這種數(shù)據(jù)結(jié)構(gòu)有時(shí)可以和其他基本數(shù)據(jù)結(jié)構(gòu)相配合职车，比如這里，使用了一個(gè)輔助的隊(duì)列鹊杖。
小結(jié)
樹的算法問題解決思路大多都是遞歸思想，因?yàn)檫@是由他的結(jié)構(gòu)所決定的扛芽。特別的骂蓖，對(duì)于樹而言，最關(guān)鍵的就是找到他的根節(jié)點(diǎn)川尖，找到了根節(jié)點(diǎn)登下，同時(shí)就可以確定其左子樹和右子樹，因此樹的問題可以轉(zhuǎn)換為左子樹和右子樹的子問題，因此可以采用遞歸的思想被芳。另外要注意的是缰贝，樹有可能會(huì)和其他基本數(shù)據(jù)結(jié)構(gòu)相配合，比如棧和隊(duì)列畔濒。
