刷题系列-Python用非递归实现二叉树后续遍历-创新互联
顺便把Python用非递归实现二叉树后续遍历也写了。
创新互联建站专注为客户提供全方位的互联网综合服务,包含不限于做网站、成都网站制作、梅里斯网络推广、小程序定制开发、梅里斯网络营销、梅里斯企业策划、梅里斯品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;创新互联建站为所有大学生创业者提供梅里斯建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com其实前序中序和后续都是针对父节点说的。比如下面这个最简单二叉树。
前序就是ABC,父节点A在前
中序就是BAC,父节点A在中间
后序就是BCA,父节点A在最后
无论多复杂二叉树,基本都是同样遍历流程。
后续遍历可以说是最简单的,从左开始遍历并放入栈,读取没有下级节点的节点值,然后把该节点推出栈,并删除和上级节点关联;然后替换栈中最上的点,并去遍历右边子节点;直到栈为空,遍历结束。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: traversalList = [] nodeList = [] # travel the node, add to node stack, if the node without any sub-node, record the val; then remove it and it's link with parnet, travel back to last one in stack. if root != None: nodeList.append(root) while nodeList != []: if nodeList[-1].left != None: nodeList.append(nodeList[-1].left ) elif nodeList[-1].right != None: nodeList.append(nodeList[-1].right) else: traversalList.append(nodeList[-1].val) currentNode = nodeList.pop() if nodeList != []: if nodeList[-1].right == currentNode: nodeList[-1].right = None elif nodeList[-1].left == currentNode: nodeList[-1].left = None return traversalList
网页标题:刷题系列-Python用非递归实现二叉树后续遍历-创新互联
网站地址:http://lswzjz.com/article/dejoji.html