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用非遞歸實現二叉樹中序遍歷代碼分享”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！