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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 bool isMirror(TreeNode* t1, TreeNode* t2) {
14 if (!t1 && !t2) return true;
15 if (!t1 || !t2) return false;
16 return (t1->val == t2->val) &&
17 isMirror(t1->right, t2->left) &&
18 isMirror(t1->left, t2->right);
19 }
20 bool isSymmetric(TreeNode* root) {
21 return isMirror(root, root);
22 }
23};This C++ solution uses a class Solution with a method isMirror to recursively check if two subtrees are mirror images. The isSymmetric method starts this check with the tree's root node.
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.
This JavaScript function uses an array as a queue to iteratively evaluate symmetry. Successive pairs of nodes are assessed for equality, swelling the queue with opposite children until determinations are final.