🎄圖論應用: 二元樹的中序拜訪 Binary Tree Inorder Traversal_LC #94

Todd Trapani on Unsplash

題目敘述 94.  Binary Tree Inorder Traversal

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

請輸出中序拜訪(In-order traversal)的拜訪序列。

中序拜訪的定義:

1.拜訪左子樹。

2.拜訪目前的節點。

3.拜訪右子樹。

示意圖

測試範例

Example 1:

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

Example 2:

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

Example 3:

Input: root = []

Output: []

Example 4:

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 inorderTraversal(self, root: TreeNode) -> List[int]:
        travarlsal_path = []

        if root :
            
            # just follow inorder definition
            travarlsal_path.extend( self.inorderTraversal( root.left ) )
            travarlsal_path .append( root.val )
            travarlsal_path.extend( self.inorderTraversal( root.right) )
            
        return travarlsal_path 

複雜度分析

時間複雜度: O(n)

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

空間複雜度: O(n)

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

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

程式碼 遞迴法 + python generator

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

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

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

複雜度分析

時間複雜度: O(n)

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

空間複雜度: O(n)

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

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

程式碼 迭代法 搭配stack

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

        while stack_inorder:

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

            elif label != "c":

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

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

                stack_inorder.append( (current.right, "r") )
                stack_inorder.append( (current, "c") )                
                stack_inorder.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 Inorder Traversal - LeetCode