This approach employs recursion to invert the binary tree. The basic idea is to traverse the tree and swap the left and right children of every node recursively. We recursively call the function on the left and right subtrees until we reach the base case, which is when the node is null.
Time Complexity: O(n) where n is the number of nodes in the tree, because each node is visited once.
Space Complexity: O(h) where h is the height of the tree, for the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* invertTree(struct TreeNode* root) {
11 if (root == NULL) return NULL;
12 struct TreeNode* left = invertTree(root->left);
13 struct TreeNode* right = invertTree(root->right);
14 root->left = right;
15 root->right = left;
16 return root;
17}This C solution defines a struct for the tree node, and then uses a recursive function invertTree that swaps the left and right children of each node starting from the root. The recursion continues until all nodes have been swapped.
The iterative approach involves using a queue or stack to traverse the tree level by level (or depth by depth) while inverting the child nodes by putting the left child in place of the right child and vice versa for each node. This is effectively a breadth-first traversal that swaps children iteratively.
Time Complexity: O(n) where n is the number of nodes in the tree.
Space Complexity: O(n) due to the queue data structure.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct QueueNode {
11 struct TreeNode *treeNode;
12 struct QueueNode *next;
13};
14
15struct Queue {
16 struct QueueNode *front, *rear;
17};
18
19struct Queue* createQueue() {
20 struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
21 queue->front = queue->rear = NULL;
22 return queue;
23}
24
25void enqueue(struct Queue* queue, struct TreeNode *node) {
26 struct QueueNode *newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
27 newNode->treeNode = node;
28 newNode->next = NULL;
29 if (queue->rear == NULL) {
30 queue->front = queue->rear = newNode;
31 return;
32 }
33 queue->rear->next = newNode;
34 queue->rear = newNode;
35}
36
37struct TreeNode *dequeue(struct Queue* queue) {
38 if (queue->front == NULL)
39 return NULL;
40 struct QueueNode* temp = queue->front;
41 struct TreeNode *node = temp->treeNode;
42 queue->front = queue->front->next;
43 if (queue->front == NULL)
44 queue->rear = NULL;
45 free(temp);
46 return node;
47}
48
49struct TreeNode* invertTree(struct TreeNode* root) {
50 if (root == NULL) return NULL;
51 struct Queue* queue = createQueue();
52 enqueue(queue, root);
53 while (queue->front != NULL) {
54 struct TreeNode* node = dequeue(queue);
55 struct TreeNode* temp = node->left;
56 node->left = node->right;
57 node->right = temp;
58 if (node->left) enqueue(queue, node->left);
59 if (node->right) enqueue(queue, node->right);
60 }
61 return root;
62}The C solution uses a queue data structure to perform a breadth-first traversal. For each node, it swaps the left and right children and then enqueues the children nodes if they exist.