刷题系列-Python中怎么通过非递归实现二叉树前序遍历
这期内容当中小编将会给大家带来有关刷题系列 - Python中怎么通过非递归实现二叉树前序遍历,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
创新互联建站主营临翔网站建设的网络公司,主营网站建设方案,app软件开发,临翔h5微信平台小程序开发搭建,临翔网站营销推广欢迎临翔等地区企业咨询
二叉树前序遍历(Binary Tree Preorder Traversal), 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。
如下图所示,前序遍历结果:ABDECF
考虑了下,要创建两个队列,一个放遍历结果,一个做类似栈作用,把路过节点放入;如果当前节点左边节点存在,读取值并放入栈继续去下个左节点, 如果没有左边节点则去右节点,同样操作;如果都没有,则栈弹出最后一个节点,删除关联,并把栈中上一个节点作为当前节点,相当于返回走。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: traversalList = [] nodeList = [] # add the first one to node list, and travel from left node first, then right; if a node without left #and righ sub-node, pop it from node list, then remove the link with parent node; traverlous finish as root list #is empty. if root != None: traversalList.append(root.val) nodeList.append(root) currentNode = root while nodeList != []: if currentNode.left != None: currentNode = currentNode.left traversalList.append(currentNode.val) nodeList.append(currentNode) elif currentNode.right != None: currentNode = currentNode.right traversalList.append(currentNode.val) nodeList.append(currentNode) else: nodeList.pop() if nodeList != []: if nodeList[-1].right == currentNode: nodeList[-1].right = None elif nodeList[-1].left == currentNode: nodeList[-1].left = None currentNode = nodeList[-1] return traversalList
上述就是小编为大家分享的刷题系列 - Python中怎么通过非递归实现二叉树前序遍历了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。
名称栏目:刷题系列-Python中怎么通过非递归实现二叉树前序遍历
网站URL:http://scyanting.com/article/pcjccd.html