【LeetCode 二叉樹專項】二叉樹的中序遍歷（94）

文章目錄

• • 1. 題目
  • • 1.1 示例
    • 1.2 說明
    • 1.3 進階
  • 2. 解法一（遞回法）
  • • 2.1 分析
    • 2.2 解答
    • 2.3 復雜度
  • 3. 解法二（迭代法）
  • • 3.1 分析
    • 3.2 解答
    • 3.3 復雜度
  • 4. 解法三（Morris 遍歷）

1. 題目

給定一個二叉樹，回傳它的 中序 遍歷，

1.1 示例

• 示例 1 1 1：

• 輸入： [1, null, 2, 3]
• 輸出： [1, 3, 2]

1.2 說明

• 來源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

1.3 進階

遞回演算法很簡單，你可以通過迭代演算法完成嗎？

2. 解法一（遞回法）

2.1 分析

類似【LeetCode 二叉樹專項】二叉樹的前序遍歷（144），二叉樹的中序遍歷使用遞回的方式很容易實作，即按照訪問 左子樹 -> 根節點 -> 右子樹 的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時候，按照同樣的方式遍歷，直到遍歷完整棵樹，可以看出，整個遍歷程序天然具有遞回的性質，因此可以直接用遞回函式來模擬這一程序，

2.2 解答

from typing import List


class TreeNode:
    def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self.tree = []

    def _inorder(self, root: TreeNode):
        if not root:
            return
        self._inorder(root.left)
        self.tree.append(root.val)
        self._inorder(root.right)

    def postorder_traversal(self, root: TreeNode) -> List[int]:
        self._inorder(root)
        return self.tree

2.3 復雜度

• 時間復雜度： O ( n ) O(n) O(n)，其中 n n n 是二叉樹的節點數，每一個節點恰好被遍歷一次，
• 空間復雜度： O ( n ) O(n) O(n) ，為遞回程序中遞回堆疊的開銷和實體屬性 self.tree 所占用空間兩者組成，其中前者平均情況下為 O ( log ? n ) O(\log n) O(logn) ，最壞情況下樹呈現鏈狀，為 O ( n ) O(n) O(n) ，

3. 解法二（迭代法）

3.1 分析

雖然迭代形式的二叉樹中序遍歷仍然借用堆疊作為輔助的資料結構，但是要比前序遍歷的迭代形式復雜一些，實作迭代形式的中序遍歷主要步驟如下：

• 步驟一： 創建一個空的堆疊 stack ；
• 步驟二： 初始化游標變數 cursor 使其參考 root ；
• 步驟三： 將 cursor 參考的節點壓堆疊并且讓 cursor 指向 cursor.left ，重復此操作直到 cursor 參考 None ；
• 步驟四： 如果 stack 非空且 cursor 參考 None ，則重復下列步驟：
  • (a)：從 stack 堆疊頂彈出節點并由 node 參考；
  • (b)：執行對彈出節點的遍歷操作；
  • (c)：使得cursor 參考 node.right ；
  • (d)：重復步驟三，
• 步驟五： 如果 cursor 參考 None 且 stack 為空，則中序遍歷完成，

為便于理解，對于形如下列形式的二叉樹，使用上述迭代步驟的具體情況如下：

		            1
		          /   \
		        2      3
		      /  \
		    4     5

• 步驟一： 創建一個空的堆疊 stack ： stack = [] ；
• 步驟二： 初始化游標變數 cursor 使其參考 root ： cursor -> 1 ；
• 步驟三： 將 cursor 參考的節點壓堆疊并且讓 cursor 指向 cursor.left ，重復此操作直到 cursor 參考 None ：
  • cursor -> 1 ；
  • 將 1 壓堆疊： stack = [1] ；
  • cursor -> 2 ；
  • 將 2 壓堆疊： stack = [1, 2] ；
  • cursor -> 4 ；
  • 將 4 壓堆疊： stack = [1, 2, 4] ；
  • cursor = None ，
• 步驟四： stack 非空且 cursor 參考 None ，重復下列步驟：
  • (a)：從 stack 堆疊頂彈出節點： stack = [1, 2] ；
  • (b)：執行對于 4 對應節點的遍歷操作；
  • (c)：使得 cursor 參考 4 對應節點的右子節點，即 cursor = None ；
  • (d)：由于 cursor = None ，步驟三不會做任何操作，
    
    
  • (a)：從 stack 堆疊頂彈出節點： stack = [1] ；
  • (b)：執行對于 2 對應節點的遍歷操作；
  • (c)：使得 cursor 參考 2 對應節點的右子節點，即 cursor -> 5 ；
  • (d)：此時 cursor -> 5 ，執行步驟三，
• 步驟三： 將 cursor 參考的節點壓堆疊并且讓 cursor 指向 cursor.left ，重復此操作直到 cursor 參考 None ：
  • cursor -> 5 ；
  • 將 5 壓堆疊： stack = [1, 5] ；
  • cursor = None ；
• 步驟四： stack 非空且 cursor 參考 None ，重復下列步驟：
  • (a)：從 stack 堆疊頂彈出節點： stack = [1] ；
  • (b)：執行對于 5 對應節點的遍歷操作；
  • (c)：使得 cursor 參考 5 對應節點的右子節點，即 cursor = None ；
  • (d)：由于 cursor = None ，步驟三不會做任何操作，
    
    
  • (a)：從 stack 堆疊頂彈出節點： stack = [] ；
  • (b)：執行對于 1 對應節點的遍歷操作；
  • (c)：使得 cursor 參考 1 對應節點的右子節點，即 cursor -> 3 ；
  • (d)：此時 cursor -> 3 ，執行步驟三，
• 步驟三： 將 cursor 參考的節點壓堆疊并且讓 cursor 指向 cursor.left ，重復此操作直到 cursor 參考 None ：
  • cursor -> 3 ；
  • 將 3 壓堆疊： stack = [3] ；
  • cursor = None ；
• 步驟四： stack 非空且 cursor 參考 None ，重復下列步驟：
  • (a)：從 stack 堆疊頂彈出節點： stack = [] ；
  • (b)：執行對于 3 對應節點的遍歷操作；
  • (c)：使得 cursor 參考 3 對應節點的右子節點，即 cursor = None ；
  • (d)：由于 cursor = None ，步驟三不會做任何操作，
• 步驟五： 最終， stack 為空且 cursor 參考 None ，中序遍歷完成，

3.2 解答

根據上述分析，得到二叉樹中序遍歷的迭代形式如下：

from typing import List


class TreeNode:
    def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self.tree = []

    def iterative_inorder(self, root: TreeNode) -> List[int]:
        if not root:
            return self.tree
        stack = []
        cursor = root
        while cursor:
            stack.append(cursor)
            cursor = cursor.left
        while stack:
            node = stack.pop()
            self.tree.append(node.val)
            cursor = node.right
            while cursor:
                stack.append(cursor)
                cursor = cursor.left
        return self.tree

實際上，上述代碼在實作步驟三時有重復的代碼實作，可進一步簡化為如下代碼：

from typing import List


class TreeNode:
    def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self.tree = []

    def succinct_iterative_inorder(self, root: TreeNode) -> List[int]:
        if not root:
            return self.tree
        stack = []
        cursor = root
        while True:
            if cursor:
                stack.append(cursor)
                cursor = cursor.left
            elif stack:
                node = stack.pop()
                self.tree.append(node.val)
                cursor = node.right
            else:
                break
        return self.tree


def main():
    """ Constructed binary tree is
                1
              /   \
             2     3
           /  \
          4    5
    """
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    sln = Solution()
    print(sln.succinct_iterative_inorder(root))  # [4, 2, 5, 1, 3]


if __name__ == '__main__':
    main()

3.3 復雜度

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

4. 解法三（Morris 遍歷）