对称二叉树

递归做法

递归三部曲：停止条件：比较完发现没有子树而且可以判断是否相等；参数：对称的左右节点；返回值：bool，是否对称

class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(left == NULL && right != NULL)return false;if(right == NULL && left != NULL)return false;if(right == NULL&&left==NULL)return true;//空if(left->val != right->val)return false;bool j1 = compare(left->left,right->right);bool j2 = compare(left->right,right->left);if((j1 == j2) && (j1 == true)){return true;}return false;}bool isSymmetric(TreeNode* root) {if(root == NULL)return true;return compare(root->left,root->right);}

迭代做法

每次入栈两个对称的部分（每次入栈顺序是左右右左），比较栈顶元素：

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;queue<TreeNode*> que;que.push(root->left);   // 将左子树头结点加入队列que.push(root->right);  // 将右子树头结点加入队列while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转TreeNode* leftNode = que.front(); que.pop();TreeNode* rightNode = que.front(); que.pop();if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的continue;}// 左右一个节点不为空，或者都不为空但数值不相同，返回falseif ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}que.push(leftNode->left);   // 加入左节点左孩子que.push(rightNode->right); // 加入右节点右孩子que.push(leftNode->right);  // 加入左节点右孩子que.push(rightNode->left);  // 加入右节点左孩子}return true;}
};