您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
顺便把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
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。