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 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public boolean isSymmetric(TreeNode root) {
10 return isMirror(root, root);
11 }
12
13 private boolean isMirror(TreeNode t1, TreeNode t2) {
14 if (t1 == null && t2 == null) return true;
15 if (t1 == null || t2 == null) return false;
16 return (t1.val == t2.val) &&
17 isMirror(t1.right, t2.left) &&
18 isMirror(t1.left, t2.right);
19 }
20}In the Java solution, class Solution uses a private helper method isMirror to check if two subtrees are mirror images. The public method isSymmetric initiates this check with the root of the binary tree.
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.
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q;
q.push(root);
q.push(root);
while (!q.empty()) {
TreeNode* t1 = q.front(); q.pop();
TreeNode* t2 = q.front(); q.pop();
if (!t1 && !t2) continue;
if (!t1 || !t2) return false;
if (t1->val != t2->val) return false;
q.push(t1->left);
q.push(t2->right);
q.push(t1->right);
q.push(t2->left);
}
return true;
}
};This C++ solution implements an iterative approach with a queue to interpret and verify the symmetry of a tree. Initial null checks precede looping through node pairs pulled from the queue, verifying their equivalence, and extending comparisons through children pushed onto the queue.