# **Leetcode筆記(Invert Binary Tree)** :::info :information_source: 題目 : Invert Binary Tree, 類型 : binary tree , 等級 : easy 日期 : 2023/03/18，2023/05/02，2023/07/03，2023/10/03，2025/02/20 ::: ### 嘗試 原本想用deque分左右邊，最後算是有自己做出來，時間複雜度O(n)，空間複雜度O(1) ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: q = deque([root]) temp = TreeNode() while q: if node.left: q.appendleft(node.left) if node.right: q.append(node.right) for i in range( len(q) // 2 ): rightnode = q.popleft() leftnode = q.pop() ``` ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root ``` 2023/05/02 ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return self.switch(root) return root def switch(self, node): if not node: return temp = TreeNode() # 交換 temp = node.left node.left = node.right node.right = temp # 傳遞 # 即使是在switch裡面呼叫switch，也需要self self.switch(node.right) self.switch(node.left) ``` 2023/07/03 目前對於遞歸的想法是 : 先從最尾端(也就是leaf)開始思考，然後忽略遞歸呼叫的那幾行，只關注它的上方與下方，上代表待操作的東西，可能是要做某些操作(或是單純return)，反正做完就依照遞歸下方的區域return參數 ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return root.right, root.left = root.left, root.right self.invertTree(root.right) self.invertTree(root.left) return root ``` 2023/10/03 ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root ``` 2025/02/20 ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None self.inverse(root) return root def inverse(self, node): if not node: return if node.left or node.right: node.left, node.right = node.right, node.left self.inverse(node.left) self.inverse(node.right) return ``` --- ### **優化** 但其實用觀察可以得到，把各左右小孩翻轉一次，連續翻轉到上面，就可以得到完整內容。 時間複雜度O(n)，空間複雜度O(n) ```python class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None # swap temp = root.right root.right = root.left root.left = temp self.invertTree(root.left) self.invertTree(root.right) return root ``` --- **:warning: 錯誤語法** :::warning 'NoneType' object has no attribute 'right' 可能是因為該treenode為null ::: **:thumbsup:學習** :::success 若只寫return，後面沒接東西，类似循环里的break，只是为了不再继续执行下面的语句 ::: **思路** **講解連結** https://www.youtube.com/watch?v=OnSn2XEQ4MY Provided by. NeetCode ###### tags: `binary tree` `easy` `leetcode`