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;
}
Input
root = [4,2,7,1,3,6,9]
Output
[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;
}
};
Input
root = [4,2,7,1,3,6,9]
Output
[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;
}
}
Input
root = [2,1,3]
Output
[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
}
Input
root = [2,1,3]
Output
[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
Input
root = []
Output
[]
#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;
}
}
}
Input
root = []
Output
[]