Symmetric Tree
Desicription
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1 2 3 4 5
| 1 / \ 2 2 / \ / \ 3 4 4 3
|
But the following [1,2,2,null,3,null,3]
is not:
Note:
Bonus points if you could solve it both recursively and iteratively.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
class Solution { private: bool isSymmetric(TreeNode* left, TreeNode* right) { if(left == NULL && right == NULL) return 1; if(left == NULL || right == NULL) return 0; if(left->val == right->val) return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left); return 0; } public: bool isSymmetric(TreeNode* root) { if(root == NULL) return 1; return isSymmetric(root->left, root->right); } };
|