Leetcode之旅|Morris 後序遍歷

03-06

1. 標題即題目描述

　　昨天在學習Morris中序遍歷的時候就想：如何用這種方法實現空間複雜度為 $O(1)$ 的方法實現二叉樹的後序遍歷呢？然後果然發現還真有這道題目。雖然題目沒有明確要求說要用Morris Traversal，但用它肯定是滿足題目要求的，所以我們今天就來記錄一下Morris後序遍歷的實現方法吧~~~

2. 演算法描述

昨天記錄的Morris中序遍歷的思想其實主要是遍歷完一個節點的左子樹的時候能找到回到這個節點的路徑，所以在迭代時會有找前驅節點這一步。但對後序遍歷來說有點複雜，因為在完成左子樹的遍歷後不是回到這個子樹的根，而是進行右子樹的遍歷。但和中序遍歷相同的是，都是先完成左子樹的遍歷，所以我們需要做一些修改，其流程圖如下：

圖1. Morris Postorder Traversal 流程圖。

　　具體來說：

1. 設置一個dummy node，使其左孩子為根節點，並初始化cur為dummy;
2. 如果cur的左孩子為空，則cur->cur.right; （和中序遍歷不同，這一步不輸出，而是需要回到其作為最右葉子節點所在子樹的根節點）
3. 如果cur的左孩子不為空，先將前驅節點p初始化為cur.left:

　　a. 如果p的右孩子不為空且不為cur，則p->pre.right; （循環此步找到左子樹中最右的葉子節點，這一步和中序遍歷相同）
　　b. 如果p的右孩子為空，p.right=cur，cur->cur.left； （這一步也和中序遍歷相同）
　　c. 如果p的右孩子為cur：
i: p.right=null（恢復樹的結構，和中序遍歷相同）；
ii: 逆序輸出從cur.left到p路徑的所有節點；

（這一步是和中序遍歷最不同的，是訪問（注意是訪問，不是輸出）完節點cur的左子樹後，需要將這個子樹的節點輸出；但輸出的順序需要從這個子樹最右的葉子節點，即前驅節點p開始，到當前節點的左孩子即可。而因為後序遍歷的性質可以看出，這個逆序輸出比較簡單，因為從cur.left到p每次都是往右孩子那邊走，走完reverse一下即可）
iii: cur->cur.right。（和中序遍歷相同）
4. 重複以上2、3步直到cur為空。

3. 代碼如下

class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ return self.morrisPost(root) def morrisPost(self,root): res = [] if not root: return res dummy = TreeNode(0) dummy.left = root cur = dummy while cur: if not cur.left: cur = cur.right continue else: p = cur.left while p.right and p.right!=cur: p = p.right if not p.right: p.right = cur cur = cur.left else: p.right = None res+=self.outReverse(cur.left,p) cur = cur.right return res

上面用了一個逆序輸出的子程序outReverse，具體如下：

def outReverse(self,s,t): x = s tmp = [x.val] while x!=t: x = x.right tmp.append(x.val) return reversed(tmp)

4. 總結

　　剛開始想怎麼後序遍歷的時候一臉蒙圈，還好現在想學習的話資料很豐富，這裡記錄下來，以作備忘。