最近在刷leetcode時，刷到了二叉樹中序遍歷的題目，所以特在此記錄一下，下面我將給出中序遍歷的遞回實作和非遞回（迭代）實作的代碼與演算法思想：
1. 中序遍歷的遞回實作:
1 class TreeNode(object): 2 def __init__(self, x): 3 self.val = x # 節點存盤的值 4 self.left = None # 左子節點 5 self.right = None # 右子節點 6 7 class solution: 8 def __init__(self): 9 self.__result_list = list() # 存放中序遍歷結果的集合 10 def inorder_traversal(self, root : TreeNode) -> list: 11 if root == None: return # 判斷節點是否為空 12 self.inorder_traversal(root.left) # 遞回遍歷左子樹 13 self.__result_list.append(root.val) # 將節點的值存放到集合中 14 self.inorder_traversal(root.right) # 遞回遍歷右子樹 15 return self.__result_list # 回傳集合
遞回實作的演算法思想：先中序遍歷左子樹，然后訪問根節點，最后訪問右子樹，
2. 中序遍歷的非遞回(迭代)實作
1 class TreeNode(object): 2 def __init__(self, x): 3 self.val = x # 節點存盤的值 4 self.left = None # 左子節點 5 self.right = None # 右子節點 6 7 class solution: 8 def inorder_traversal1(self, root : TreeNode) -> list: 9 if root == None: return 10 stack = list() # 存放節點的堆疊 11 result_list = list() # 存放節點值的集合 12 while root != None and result_list: 13 while root != None : 14 stack.append(root) # 將該節點壓入堆疊中 15 root = root.left # (指標)指向左子節點 16 new_root = stack.pop() # 彈出堆疊頂節點 17 result_list.append(new_root.val) # 將該節點的值加入結果集合 18 root = new_root.right # (指標)指向被彈出節點的右子節點 19 return result_list # 回傳結果集合
迭代實作的演算法思想：
1. 先將根節點壓入堆疊中 , 接著掃描根節點的左子節點
2. 若左子節點不為空則重復上述操作
3. 若左自節點為空則彈出堆疊頂節點，并掃描被彈出節點的右子節點
4. 回傳此程序直到堆疊為空為止
好了，以上就是中序遍歷的遞回與非遞回兩種方式的實作方法了，如有錯誤還望指正，謝謝，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/183605.html
標籤：Python
上一篇：初學Python，聽從大佬的意見自己整合的好用的代碼片段，好用到哭！
下一篇：python爬蟲實戰<一>