後序遍歷二叉樹

　　後序遍歷是二叉樹遍歷的一種，也叫做後根遍歷、後序周遊，可記做左右根。後序遍歷有遞迴演算法和非遞迴演算法兩種。在二叉樹中，先左後右再根。巧記：左右根。序遍歷的非遞迴演算法是三種順序中最複雜的，原因在於，後序遍歷是先訪問左、右子樹,再訪問根節點，而在非遞迴演算法中，利用棧回退到時，並不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，如果從左子樹回退到根節點，此時就應該去訪問右子樹，而如果從右子樹回退到根節點，此時就應該訪問根節點。所以相比前序和後序，必須得在壓棧時新增資訊，以便在退棧時可以知道是從左子樹返

　　一、先序遍歷

　　1、先序遍歷，按照最優先順序沿一定路徑經過路徑上所有的站，在二叉樹中，先根後左再右；

　　2、首先訪問根結點然後遍歷左子樹，最後遍歷右子樹，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；

　　3、也稱先根遍歷、前序遍歷。

　　二、後序遍歷

　　1、後序遍歷是二叉樹遍歷的一種，有遞迴演算法和非遞迴演算法兩種。在二叉樹中，先左後右再根；

　　2、後序遍歷首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點；

　　3、也稱做後根遍歷、後序周遊。

　　前序遍歷：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

　　中序遍歷：中序遍歷左子樹，然後訪問根節點，再中序遍歷右子樹。

　　後序遍歷：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。