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用非递归实现二叉树中序遍历

原文：https://www.cnblogs.com/chenguopa/p/15239983.html