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 = Noneclass 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用非递归实现二叉树中序遍历代码分享"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！