顺便把Python用非递归实现二叉树后续遍历也写了。

其实前序中序和后续都是针对父节点说的。比如下面这个最简单二叉树。

前序就是ABC，父节点A在前

中序就是BAC，父节点A在中间

后序就是BCA，父节点A在最后

无论多复杂二叉树，基本都是同样遍历流程。

后续遍历可以说是最简单的，从左开始遍历并放入栈，读取没有下级节点的节点值，然后把该节点推出栈，并删除和上级节点关联；然后替换栈中最上的点，并去遍历右边子节点；直到栈为空，遍历结束。

#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassSolution:defpostorderTraversal(self,root:TreeNode)->List[int]:traversalList=[]nodeList=[]#travelthenode,addtonodestack,ifthenodewithoutanysub-node,recordtheval;thenremoveitandit'slinkwithparnet,travelbacktolastoneinstack.ifroot!=None:nodeList.append(root)whilenodeList!=[]:ifnodeList[-1].left!=None:nodeList.append(nodeList[-1].left)elifnodeList[-1].right!=None:nodeList.append(nodeList[-1].right)else:traversalList.append(nodeList[-1].val)currentNode=nodeList.pop()ifnodeList!=[]:ifnodeList[-1].right==currentNode:nodeList[-1].right=NoneelifnodeList[-1].left==currentNode:nodeList[-1].left=NonereturntraversalList