後序遍歷二叉樹

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