Algorithm

Problem Name: 226. Invert Binary Tree

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

Example 1:

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

Example 2:

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

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};

struct QueueNode {
void * ptr;
struct QueueNode *next;
};

struct Queue{
struct QueueNode *front;
struct QueueNode *tail;
};

void push(struct Queue *queue, void *new_val) {

struct QueueNode *new_node = (struct QueueNode *)malloc(sizeof(struct QueueNode));

new_node->ptr = new_val;
new_node->next = NULL;

if (queue->tail != NULL) {
queue->tail->next = new_node;
}

queue->tail = new_node;

if (queue->front == NULL) {
queue->front = new_node;
}
}

void * pop(struct Queue * queue) {
void *ans;
if (queue->front == NULL) {
ans = NULL;
}
else {
ans = queue->front->ptr;
struct QueueNode *tmp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->tail = NULL;
}
free(tmp);
}

return ans;
}

void printTreeLevelOrder(struct TreeNode *root) {

struct Queue q;
q.front = q.tail = NULL;
push(&q, root);

while (q.front != NULL) {
struct TreeNode * p = (struct TreeNode *)pop(&q);

if (p) {
printf("%d", p->val);

push(&q, p->left);
push(&q, p->right);
}
else {
printf("#");
}
}

printf("\n");
}

struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) return NULL;

struct Queue q;
q.front = q.tail = NULL;

push(&q, root);

while (q.front != NULL) { /* queue is not empty */
struct TreeNode * p = (struct TreeNode *)pop(&q);

if (p) {
struct TreeNode * t = p->left;
p->left = p->right;
p->right = t;

push(&q, p->left);
push(&q, p->right);
}
}

return root;
}

/* recursive method */
struct TreeNode* invertTree_r(struct TreeNode* root) {
if (root == NULL) return NULL;

struct TreeNode *t = root->left;
root->left = root->right;;
root->right = t;

invertTree_r(root->left);
invertTree_r(root->right);
return root;
}

int main() {

struct TreeNode *root = (struct TreeNode *)calloc(5, sizeof(struct TreeNode));
struct TreeNode *p = root;

p->left = root + 1;
p->right = root + 2;

p = root + 2;
p->left = root + 3;

p = root + 3;
p->left = root + 4;

root->val = 1;
(root + 1)->val = 4;
(root + 2)->val = 3;
(root + 3)->val = 2;
(root + 4)->val = 5;

/* 143##2#5# */
printTreeLevelOrder(root);

invertTree(root);

/* 134#2###5 */
printTreeLevelOrder(root);

return 0;
}
``````
Copy The Code &

Input

cmd
root = [4,2,7,1,3,6,9]

Output

cmd
[4,7,2,9,6,3,1]

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};
``````
Copy The Code &

Input

cmd
root = [4,2,7,1,3,6,9]

Output

cmd
[4,7,2,9,6,3,1]

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode right = root.right;
root.right = root.left;
root.left = right;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
``````
Copy The Code &

Input

cmd
root = [2,1,3]

Output

cmd
[2,3,1]

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const invertTree = function (root) {
if (root) {
;[root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
}
return root
}
``````
Copy The Code &

Input

cmd
root = [2,1,3]

Output

cmd
[2,3,1]

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root: return
root.left, root.right= root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

#6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0226_InvertBinaryTree
{
public TreeNode InvertTree(TreeNode root)
{
if (root == null) return null;

var left = root.left;
root.left = InvertTree(root.right);
root.right = InvertTree(left);

return root;
}
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]