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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode InvertTree(TreeNode root) {
10 if (root == null) return null;
11 TreeNode left = InvertTree(root.left);
12 TreeNode right = InvertTree(root.right);
13 root.left = right;
14 root.right = left;
15 return root;
16 }
17}In this C# solution, the TreeNode class is defined with fields for value, left, and right nodes. The method InvertTree swaps the left and right children recursively.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public TreeNode InvertTree(TreeNode root) {
13 if (root == null) return null;
14 Queue<TreeNode> queue = new Queue<TreeNode>();
15 queue.Enqueue(root);
16 while (queue.Count > 0) {
17 TreeNode node = queue.Dequeue();
18 TreeNode temp = node.left;
19 node.left = node.right;
20 node.right = temp;
21 if (node.left != null) queue.Enqueue(node.left);
22 if (node.right != null) queue.Enqueue(node.right);
23 }
24 return root;
25 }
26}This C# solution uses a Queue from System.Collections.Generic to carry out an iterative breadth-first tree inversion. It iteratively accesses nodes level by level and swaps them using a temporary variable.