题意
给定一棵二叉树,判断是否对称
分析
对一棵子树做镜像,然后判断左右子树是否相同。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void mirror(TreeNode* root){
if(root == NULL || root->left == NULL && root->right == NULL)return;
mirror(root->left);
mirror(root->right);
swap(root->left, root->right);
}
bool isSame(TreeNode* p1, TreeNode* p2){
if(p1 == NULL && p2 == NULL)return true;
if(p1 == NULL || p2 == NULL)return false;
return (p1->val == p2->val) && isSame(p1->left, p2->left) && isSame(p1->right, p2->right);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL || root->left == NULL && root->right == NULL)return true;
mirror(root->left);
return isSame(root->left, root->right);
}
};
法二:对称遍历
定义对称前序遍历,根节点,右子树,左子树
对左子树前序遍历,右子树对称前序遍历,比较遍历序列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> p1;
vector<int> p2;
void dfs1(TreeNode* root){
if(root == NULL){
p1.push_back(-1);
return;
};
p1.push_back(root->val);
dfs1(root->left);
dfs1(root->right);
}
void dfs2(TreeNode* root){
if(root == NULL){
p2.push_back(-1);
return;
}
p2.push_back(root->val);
dfs2(root->right);
dfs2(root->left);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL || root->left == NULL && root->right == NULL)return true;
dfs1(root->left);
dfs2(root->right);
int len1 = p1.size(), len2 = p2.size();
if(len1 != len2)return false;
for(int i = 0; i < len1; i ++){
if(p1[i] != p2[i])return false;
}
return true;
}
};