:orphan:

Invert Binary Tree
==================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/invert-binary-tree/

Given the ``root`` of a binary tree, invert the tree, and return *its
root*.

 

**Example 1:**

|image1|

::


   Input: root = [4,2,7,1,3,6,9]
   Output: [4,7,2,9,6,3,1]

**Example 2:**

|image2|

::


   Input: root = [2,1,3]
   Output: [2,3,1]

**Example 3:**

::


   Input: root = []
   Output: []

 

**Constraints:**

- The number of nodes in the tree is in the range ``[0, 100]``.
- ``-100 <= Node.val <= 100``

.. |image1| image:: https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution
--------
Observe that when we invert the tree, we can do it in 2 steps:
1. Swap the left and right children of the root.
2. Invert the left and right subtrees.
This gives a recursive algorithm to invert a binary tree.

Code
----

.. literalinclude:: ../problems/easy/invert-binary-tree/invert_binary_tree__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from invert_binary_tree__approach_1 import TreeNode, invertTree
>>> root = TreeNode.from_list([4, 2, 7, 1, 3, 6, 9])
>>> invertTree(root)
TreeNode(4, TreeNode(7, TreeNode(9, None, None), TreeNode(6, None, None)), TreeNode(2, TreeNode(3, None, None), TreeNode(1, None, None)))
>>> root = TreeNode.from_list([2, 1, 3])
>>> invertTree(root)
TreeNode(2, TreeNode(3, None, None), TreeNode(1, None, None))
>>> root = TreeNode.from_list([])
>>> invertTree(root) is None
True

Complexity
----------
| :math:`n` is the number of nodes in the tree
| Time: :math:`O(n)` — visit every node
| Auxiliary Space: :math:`O(1)`

.. autoclass:: invert_binary_tree__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: invert_binary_tree__approach_1.invertTree