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 <stdbool.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9bool isMirror(struct TreeNode* t1, struct TreeNode* t2) {
10 if (t1 == NULL && t2 == NULL) return true;
11 if (t1 == NULL || t2 == NULL) return false;
12 return (t1->val == t2->val) &&
13 isMirror(t1->right, t2->left) &&
14 isMirror(t1->left, t2->right);
15}
16
17bool isSymmetric(struct TreeNode* root) {
18 return isMirror(root, root);
19}This C code defines a recursive function isMirror that checks if two trees are mirror images. The isSymmetric function calls isMirror with the root node passed twice. The function checks if both nodes are null (returns true if so) or if one is null (returns false). It then checks if the values are the same and recursively calls isMirror on the opposite children nodes.
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 C solution employs a queue data structure for comparing values of nodes iteratively. A newly defined data structure and its pertinent functions encapsulate the queue. The code mimics the recursive solution’s pattern: null-checking nodes, confirming equality of values, and inserting children appropriately for subsequent comparisons.