題目

  • 題目連結
  • 目標函式 : invertTree(root)
    • Input : root: TreeNode
    • Output : TreeNode

解題概念

  • 題意 : 給予一 Binary Tree 的 root，對其進行反轉並回傳 root
  • 此題是在操作 Binary Tree範疇中很經典的一題

我的寫法

  • 想法 : 使用遞迴的方式
    1. 若 root 為空，則直接回傳 root
    2. 否則交換 root.left 與 root.right
    3. 最後再回傳 root
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def invertTree(self, root):
        if root == None: return root

        leftTree = self.invertTree(root.right)
        rightTree = self.invertTree(root.left)

        root.left = leftTree
        root.right = rightTree

        return root
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 21 ms (faster than 29.37%)
    • Memory Usage: 13.6 MB (more than 19.95%)

解答 or 其他優秀寫法 - Part1

  • 想法 : 基本上與我的想法相同，但寫法更為簡潔
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    def invertTree(self, root):
        
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

        return root
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 19 ms (faster than 55.8%)
    • Memory Usage: 13.2 MB (more than 87.87%)

解答 or 其他優秀寫法 - Part2

  • 想法 : 採用 Stack 與 BFS(Breadth-First Search) 的寫法
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    def invertTree(self, root):
        stack = [root]
        while stack:
            node = stack.pop() # Pop 一元素
            if node: # 若 node 非空
                node.left, node.right = node.right, node.left # 交換左右子點
                stack += node.left, node.right # 將左右子點 push 到 stack 中
        return root
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 19 ms (faster than 55.8%)
    • Memory Usage: 13.4 MB (more than 52.26%)