1.描述
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 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
2.方法一
2.1分析
将右子树反转,然后判断左子树和反转后的右子树是否相同。
2.2代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void reversal(struct TreeNode* root) {
if (NULL == root) return ;
reversal(root->left);
reversal(root->right);
struct TreeNode* tmp;
tmp = root->left;
root->left = root->right;
root->right = tmp;
}
bool isSameTree(struct TreeNode* tree1, struct TreeNode* tree2) {
if (NULL == tree1 && NULL == tree2) return true;
if (NULL == tree1 || NULL == tree2) return false;
if (tree1->val != tree2->val) return false;
bool left = isSameTree(tree1->left, tree2->left);
bool right = isSameTree(tree1->right, tree2->right);
return left && right;
}
bool isSymmetric(struct TreeNode* root) {
if (NULL == root) return true;
if (NULL == root->left && NULL == root->right) return true;
if (NULL == root->left || NULL == root->right) return false;
reversal(root->right);
return isSameTree(root->left, root->right);
}
3.方法二
3.1分析
层次遍历二叉树,判断每层的元素是否对称。
3.2代码
4.方法三
4.1分析
简单递归
4.2代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSymmetricRL(struct TreeNode* root1, struct TreeNode* root2) {
if (NULL == root1 && NULL == root2) return true;
if (NULL == root1 || NULL == root2) return false;
if (root1->val != root2->val) return false;
return isSymmetricRL(root1->left, root2->right) && isSymmetricRL(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root) {
if (NULL == root) return true;
return isSymmetricRL(root->left, root->right);
}
网友评论