Python用非递归实现二叉树中序遍历代码分享-创新互联
这篇文章主要介绍“Python用非递归实现二叉树中序遍历代码分享”,在日常操作中,相信很多人在Python用非递归实现二叉树中序遍历代码分享问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python用非递归实现二叉树中序遍历代码分享”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名注册、雅安服务器托管、营销软件、网站建设、百色网站维护、网站推广。中序遍历其实和就是先找到最左边节点,然后是其上级节点,再到上级节点的右边节点。
比如下面的中序遍历结果就是 DBEAFC
非递归实现逻辑,我想的这个比较笨。就是用一个队列做栈,先按照左边遍历压入栈中;当到左边叶子节点时候,读取并删除关联;推出栈回到上一级节点,如果上级节点没有右节点,则读取继续删除;如果有,则遍历右节点;为了防止右边遍历返回时候再次读取父节点;要记录下上次被推出节点,如果是右节点,则不读取父节点信息。
代码写的很难看,不去雕琢了,见笑。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: traversalList = [] nodeList = [] # similar as Preorder traversal, the only change is that the value of node is recored when the node doesn't have left sub-node; new object removedNode as popped node, if a node's right sub-node is removedNode, then it should be popped both. if root != None: nodeList.append(root) currentNode = root removedNode = None while nodeList != []: if currentNode.left != None: currentNode = currentNode.left nodeList.append(currentNode) elif currentNode.right == None or currentNode.right == removedNode: if currentNode.right == None: traversalList.append(currentNode.val) removedNode = nodeList.pop() if nodeList!= []: currentNode = nodeList[-1] currentNode.left = None elif currentNode.right !=None: traversalList.append(currentNode.val) currentNode = currentNode.right nodeList.append(currentNode) return traversalList
到此,关于“Python用非递归实现二叉树中序遍历代码分享”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联-成都网站建设公司网站,小编会继续努力为大家带来更多实用的文章!
当前标题:Python用非递归实现二叉树中序遍历代码分享-创新互联
文章源于:http://scjbc.cn/article/ddgeps.html