秋招記錄
二叉樹的周遊是筆試常見的題目了，記錄一下一勞永逸
對一棵二叉樹進行周遊，我們可以采取3種順序進行周遊，分别是前序周遊、中序周遊和後序周遊。
這三種方式是以通路父節點的順序來進行命名的。
假設父節點是N，左節點是L，右節點是R，那麼對應的通路周遊順序如下：
前序周遊：中左右 N>L>R
中序周遊：左中右 L>N>R
後序周遊：左右中 L>R>N
總結：
1.先左後右是一定的，父節點的位置決定了前中後
2.利用前序周遊可以得到根節點，就是第一個
3.利用後序周遊可以得到根節點，最後一個
4.确認了根節點，利用中序周遊可以得到左子樹和右子樹
5.對左子樹和右子樹分别做前面3點的分析和拆分，相當于做遞歸，我們就可以重建出完整的二叉樹
例題：前序周遊的順序是: CABGHEDF 中序周遊的順序是: GHBACDEF
第一步：根節點是C 左包括 GHBA 右包括 DEF
第二步：把左子樹當做一個完整的二叉樹再看，A是左子樹的根節點，而GHB都在A的左邊，同理右子樹的根節點是E，左右分别是D和F
第三步：根據前兩步的經驗，對于每個小子樹都采用同樣的方式，最後得到完整的二叉樹：
關鍵：
**記住前中後序所對應的節點周遊順序！
前中後是指N的位置，左右不變！**