---
# System prepended metadata

title: '**Leetcode筆記(Invert Binary Tree)**'
tags: [easy, binary tree, leetcode]

---

# **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`