0145. Binary Tree Postorder Traversal - chasel2361/leetcode GitHub Wiki

Given a binary tree, return the postorder traversal of its nodes' values.

Example:
Input: [1,null,2,3]
Output: [3,2,1]

前面做了 Preorder 的題目，想說 Postorder 應該不會差太多來寫看看，結果差很多啊哈哈哈

首先是一個偷吃步的解法，Postorder 的尋訪順序是"左 - 右 - 根"，其實可以用"根 - 右 - 左"的順序把二元樹存下來，再反過來輸出就好。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        traversal = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                traversal.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
            
        return traversal[::-1]

這個解法的時間與空間複雜度皆為 O(N)

---

如果不偷吃步的話做法會稍微複雜一點，Postorder 的尋訪方式如上述為"左 - 右 - 根"，但必定要先找到根才能找到左右子樹，因此可以對 stack 中的節點做一個"是否已尋訪過"的布林標記，如果 pop 出來的節點存在且已經尋訪過，那就將之輸出

[1] 將 stack 改為儲存節點以及布林值的 tuple
[2] 由於節點的左右子樹可能不存在， 所以需要先檢驗 node 的存在
[3] 若 node 已被尋訪過，將其值存入 traversal
[4] 若 node 未被尋訪過，將其標記為已尋訪、存入 stack，將其右子樹及左子樹標記為未尋訪、存入 stack

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        traversal = []
        stack = [(root, False)]  #[1]
            
        while stack:
            node, visited = stack.pop()
            if node:  #[2]
                if visited: 
                    traversal.append(node.val)  #[3]
                else:
                    stack.extend([(node, True), 
                                  (node.right, False), 
                                  (node.left, False)])  #[4]
        return traversal

這個做法的時間與空間複雜度也是 O(N)，但因為 stack 的內容改為 tuple，會跑得稍慢一點，也更占空間