101. Symmetric Tree
1. Description
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
2. Follow Up
- Solve it both recursively and iteratively.
3. Solutions
Recursive
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (root != nullptr) {
return _is_same(root->left, root->right);
} else {
return true;
}
}
private:
bool _is_same(TreeNode *root1, TreeNode *root2) {
if (root1 == nullptr && root2 == nullptr) {
return true;
} else if (root1 != nullptr && root2 != nullptr && root1->val == root2->val) {
return _is_same(root1->left, root2->right) && _is_same(root1->right, root2->left);
} else {
return false;
}
}
};