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