Sponsored
Sponsored
This approach uses recursion to compare the left subtree and right subtree of the binary tree. For two trees to be mirror images, the following three conditions must be true:
Recursion is an elegant way to check this condition for each node in the tree.
Time Complexity: O(n), where n is the number of nodes in the binary tree, since we traverse every node once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion call stack.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def isSymmetric(self, root: TreeNode) -> bool:
9 return self.isMirror(root, root)
10
11 def isMirror(self, t1: TreeNode, t2: TreeNode) -> bool:
12 if t1 is None and t2 is None:
13 return True
14 if t1 is None or t2 is None:
15 return False
16 return (t1.val == t2.val and
17 self.isMirror(t1.right, t2.left) and
18 self.isMirror(t1.left, t2.right))In this Python code, a Solution class contains a public method isSymmetric and a private helper method isMirror. isMirror checks whether two subtrees are mirror images of each other recursively.
This approach utilizes a queue data structure to iteratively compare nodes in the binary tree. It behaves like the recursive method mirroring trees, but it exchanges recursion for a loop that dequeues two nodes at a time.
Time Complexity: O(n), n being indicative of the number of nodes enumerated.
Space Complexity: O(n), underscored by the queue's need for storing nodes in tandem with iteration.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsSymmetric(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
queue.Enqueue(root);
while (queue.Count != 0) {
TreeNode t1 = queue.Dequeue();
TreeNode t2 = queue.Dequeue();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
queue.Enqueue(t1.left);
queue.Enqueue(t2.right);
queue.Enqueue(t1.right);
queue.Enqueue(t2.left);
}
return true;
}
}Utilizing Queue from the C# library, this solution iteratively evaluates a tree's symmetry. Nodes are enqueued and dequeued in pairs to assess comparability, verifying left and right elements throughout.