🎄圖論應用: 樹的後序拜訪 N-ary Tree Postorder Traversal_Leetcode #590

Alec Bennett on Unsplash

題目敘述 N-ary Tree Postorder Traversal

題目給定一個N-ary(每個節點最多N個子樹)的樹根。

請返回後序拜訪這棵樹的軌跡。

推廣後的後序拜訪的定義:

1.從左到右依序拜訪所有子樹。

2.拜訪目前的節點。

示意圖

測試範例

Example 1:

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

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

約束條件

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].

節點總數目介於0~一萬。

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

• 0 <= Node.val <= 10^4

節點值都介於0 ~ 一萬之間。

• The height of the n-ary tree is less than or equal to 1000.

樹高 <= 1000

進階提問

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

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

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

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

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

推廣後的後序拜訪的定義:

1.從左到右依序拜訪所有子樹。

2.拜訪目前的節點。

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

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        
        if not root:
            # base case:
            # empty node or empty tree
            return []
        
        else:
            # general case:

            path = []

            # Traverse children with postorder:
            for child in root.children:
                path += self.postorder( child )
            
            # Travese current node with postorder:
            path.append( root.val )

            return path

複雜度分析

時間複雜度: O(n)

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

空間複雜度: O(n)

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

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

程式碼 迭代法 搭配stack

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        
        # base case:
        traversal_stack = [ (root, 'init') ]
        
        path = []
        
        # general case:
        while traversal_stack:
            
            current, label = traversal_stack.pop()
            
            if current:
            
                if label != 'cur':
                    
                    
                    # DFS with postorder
                    # left child, ...,right child, current node

                    # Stack is of Last In First Out,
                    # thus push in reverse of postorder
                    
                    traversal_stack.append( (current, 'cur') )
                    
                    for i in range( len(current.children)-1, -1, -1):
                        traversal_stack.append( (current.children[i],'child' ) )
                        
                else:
                    
                    path.append( current.val)
                                
        return path
                

複雜度分析

時間複雜度: O(n)

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

空間複雜度: O(n)

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

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

結語

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

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

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

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

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

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

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

Reference

[1] N-ary Tree Postorder Traversal - LeetCode