# 0226. Invert Binary Tree

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Invery Binary Tree](https://leetcode.com/problems/invert-binary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0226-invert-binary-tree)

Given the `root` of a binary tree, invert the tree, and return *its root*.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Swap left- and right-pointer** in each iteration.
{% endhint %}
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="​  🤖 Python3" %}

```python
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # (base case)
        if (not root) or (not root.left and not root.right): return root
        
        # ==================================================
        #  Binary Tree                       (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [root]
        while stack:
            node = stack.pop()
                
            node.left, node.right = node.right, node.left
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            
        return root
            
        '''
        # ==================================================
        #  Tree                              (Recursive)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */

    public TreeNode invertTree(TreeNode root) {
        if((root == null) || (root.left == null && root.right == null)) return root;
        
        TreeNode tmp = root.left;
        root.left  = root.right;
        root.right = tmp;
           
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}
```

{% endtab %}
{% endtabs %}