顺便把Python用非递归实现二叉树后续遍历也写了。
公司主营业务:网站设计制作、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出衢州免费做网站回馈大家。
其实前序中序和后续都是针对父节点说的。比如下面这个最简单二叉树。
前序就是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用非递归实现二叉树后续遍历
标题网址:https://www.cdcxhl.com/article44/ieocee.html
成都网站建设公司_创新互联,为您提供网站设计、外贸网站建设、服务器托管、营销型网站建设、App设计、全网营销推广
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联