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 <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10TreeNode* invertTree(TreeNode* root) {
11 if (root == NULL) return NULL;
12 TreeNode* left = invertTree(root->left);
13 TreeNode* right = invertTree(root->right);
14 root->left = right;
15 root->right = left;
16 return root;
17}The C++ solution has a TreeNode struct defining the structure of a tree node. The invertTree function uses recursion to swap left and right children, mirroring the logic used in the C solution.
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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def invertTree(self, root: TreeNode) -> TreeNode:
11 if root is None:
12 return None
13 queue = deque([root])
14 while queue:
15 current = queue.popleft()
16 current.left, current.right = current.right, current.left
17 if current.left:
18 queue.append(current.left)
19 if current.right:
20 queue.append(current.right)
21 return rootIn this Python solution, the deque from the collections module is used to implement the queue-based iterative approach. Nodes are processed in a breadth-first manner and swapped in place.