Leetcode 二叉樹的后序遍歷

0 題目描述

Leetcode原題鏈接：二叉樹的后序遍歷

二叉樹的后序遍歷：按照訪問左子樹——右子樹——根節點的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時候，我們按照同樣的方式遍歷，直到遍歷完整棵樹，因此整個遍歷程序天然具有遞回的性質，我們可以直接用遞回函式來模擬這一程序，

1 遞回解法

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: 
            return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

演算法復雜度
時間復雜度： O ( n ) O(n) O(n)，其中 n n n 為二叉樹節點的個數，二叉樹的遍歷中每個節點會被訪問一次且只會被訪問一次，
空間復雜度： O ( n ) O(n) O(n)，空間復雜度取決于遞回的堆疊深度，而堆疊深度在二叉樹為一條鏈的情況下會達到 O ( n ) O(n) O(n)的級別，

2 迭代解法（堆疊）

我們也可以用迭代的方式實作方法一的遞回函式，兩種方式是等價的，區別在于遞回的時候隱式地維護了一個堆疊，而我們在迭代的時候需要顯式地將這個堆疊模擬出來，其余的實作與細節都相同，具體可以參考下面的代碼，

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        White, Gray = 0, 1
        res = []
        stack = [(White, root)]
        while stack:
            color, node = stack.pop()
            if not node: continue
            if color == White:
                stack.append((Gray, node))
                stack.append((White, node.right))
                stack.append((White, node.left))
            else:
                res.append(node.val)
        return res

演算法復雜度
時間復雜度：訪問每個節點恰好一次，時間復雜度為 O ( N ) O(N) O(N)，其中 N N N是節點的個數，也就是樹的大小，
空間復雜度：取決于樹的結構，最壞情況存盤整棵樹，因此空間復雜度是 O ( N ) O(N) O(N)，

3 Morris 后序遍歷

有一種巧妙的方法可以在線性時間內，只占用常數空間來實作后序遍歷，這種方法即Morris遍歷，

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def addPath(node: TreeNode):
            count = 0
            while node:
                count += 1
                res.append(node.val)
                node = node.right
            i, j = len(res) - count, len(res) - 1
            while i < j:
                res[i], res[j] = res[j], res[i]
                i += 1
                j -= 1

        if not root: return []
        node, res = root, []
        while node:
            pre = node.left
            if pre:
                while pre.right and pre.right is not node:
                    pre = pre.right
                if not pre.right:
                    pre.right = node
                    node = node.left
                    continue
                else:
                    pre.right = None
                    addPath(node.left)
            node = node.right

        addPath(root)
        return res

演算法復雜度
時間復雜度： O ( n ) O(n) O(n)，其中 n n n是二叉樹的節點數，沒有左子樹的節點只被訪問一次，有左子樹的節點被訪問兩次，
空間復雜度： O ( 1 ) O(1) O(1)，只操作已經存在的指標（樹的空閑指標），因此只需要常數的額外空間，

參考資料

二叉樹的前序遍歷
二叉樹的中序遍歷 – Python實作三種解法