🎄圖論應用: 二元樹的後序拜訪 Binary Tree Postorder Traversal_LC #145

Ricky LK on Unsplash

題目敘述 145. Binary Tree Postorder Traversal

題目給定一個二元樹的根結點。

請輸出後序拜訪(Post-order traversal)的拜訪序列。

後序拜訪的定義:

1.拜訪左子樹。

2.拜訪右子樹。

3.拜訪目前的節點。

示意圖

測試範例

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

約束條件

Constraints:

• The number of the nodes in the tree is in the range [0, 100].

節點總數目介於0~100之間。

請注意，題目有可能給一個空樹。

• -100 <= Node.val <= 100

節點值都介於-100 ~ 100之間。

進階提問

Follow up: Recursive solution is trivial, could you do it iteratively?

遞迴的方式很簡單，請問你能使用迭代的方式完成後序拜訪嗎?

演算法 遞迴法 依據定義實現

其實不管是哪一層，哪一個節點，後序拜訪的規則都是相同的，

只要根據後序拜訪的定義，寫出遞迴function即可。

後序拜訪的定義:

1.拜訪左子樹。

2.拜訪右子樹。

3.拜訪目前的節點。

程式碼 遞迴法 依據定義實現

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        
        traversal_path = []
        if not root:
            # empty node or empty tree
            return []

        else:
            # DFS with postorder 
            # left child, right child, current node
            
            traversal_path.extend( self.postorderTraversal( root.left ) )
            traversal_path.extend( self.postorderTraversal( root.right ) )
            
            traversal_path.append( root.val )
            
        return traversal_path

複雜度分析

時間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

空間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。

程式碼 遞迴法 + python generator

對python generator概念和yield與unpacking *語法熟悉的讀者，

也可使用generator生成器的概念，直接在遞迴時動態輸出拜訪結果。

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        def postorder( node ):
            
            ## Base case on empty node or empty tree
            if not node:
                return 
            
            ## General cases
            yield from postorder(node.left)
            yield from postorder(node.right)
            yield node.val
        
        # --------------------------------------
        
        return [*postorder(root)]

複雜度分析

時間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

空間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。

程式碼 迭代法 搭配stack

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        
        traversal_path = []
        stack_postorder = [ (root, "init") ]

        while stack_postorder:

            current, label = stack_postorder.pop()
            
            if not current:
                # empty node
                continue

            elif label != "c":

                # DFS with postorder
                # left child, right child, current node

                # Stack is of Last In First Out,
                # thus push in reverse of postorder

                stack_postorder.append( (current, "c") )
                stack_postorder.append( (current.right, "r") )
                stack_postorder.append( (current.left, "l") )
            
            elif label == "c":

                traversal_path.append( current.val )

        return traversal_path

複雜度分析

時間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

空間複雜度: O(n)

每個節點拜訪一次，總共n個節點。

當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最長的stack長度。

結語

其實常見的tree traversal(前序、中序、後序拜訪)，

背後的核心觀念都是相同的。

Tree traversal其實就是探索整顆樹的搜索空間，也可以說是探索整顆樹，

只是指定順序略有不同而已。

有興趣的讀者可參考這篇文章，會用更宏觀的觀點看待樹的拜訪。

二元樹的拜訪 結合 DFS深度優先模板

Reference

[1] Binary Tree Postorder Traversal - LeetCode