一.题目：对称二叉树
2.算法思想
（1）（递归）
对称的条件：
1.根结点相同
2. r1树的左子树同r2树的右子树，r1树的右子树同r2树的左子树。
所以可以用递归实现，注意结构体指针引用元素要用->而不能用小点
（2）（迭代）
用队列迭代，当队列中每两个连续的结点都是相同值时则互为镜像。该队列的处理：每次提取子树左结点A和右结点B和然后比较，然后将A结点的左结点和B结点的右结点插入队列，将A结点的右结点和B结点的左结点插入队列，直至比较到队列为空位置。
3.代码
（1）递归版本
/** * 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: bool isSymmetric(TreeNode* root) { if(root==NULL) return true; return isSym(root->left,root->right); } //判断根结点为r1和r2的两棵树是否是对称的 bool isSym(TreeNode* r1,TreeNode* r2){ if(r1==NULL&&r2==NULL) return true;//能通过第一行则说明两者都不是空 if(r1==NULL||r2==NULL) return false; //对称的条件： //1.根结点相同 2.1树的左子树同2树的右子树(右同) return r1->val==r2->val && isSym(r1->left,r2->right)&&isSym(r1->right,r2->left); } };
（2）迭代版本
class Solution { public: bool isSymmetric(TreeNode* root) { std::queue<TreeNode*> q; q.push(root); q.push(root); while(!q.empty())//队列空则结束循环 { TreeNode* t1 = q.front(); q.pop(); TreeNode* t2 = q.front(); q.pop(); if(t1==NULL && t2==NULL) continue;//continue跳过这一轮 if(t1==NULL || t2==NULL) return false;//一个空一个不空则结束这层递归 if(t1->val != t2->val) return false;//此时队列中相邻的两个元素不同则return q.push(t1->left); q.push(t2->right); q.push(t1->right); q.push(t2->left); } return true; } };
如果是反转二叉树：
1./** * 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: TreeNode* mirrorTree(TreeNode* root) { if(root == NULL){ return NULL; } swap(root->left, root->right); mirrorTree(root->left); mirrorTree(root->right); return root; } };
