题目描述
给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称） 例如：下面这棵二叉树是对称的
下面这棵二叉树不对称。
备注： 希望你可以用递归和迭代两种方法解决这个问题
示例1 输入 {1,2,2} 输出 true 示例2 输入 {1,2,3,3,#,2,#} 输出 false
一、递归的方法： 1、思路：(树的结点值都为个位数)
假如树在一张纸上，对折纸后结点重合，重合处值相等，满足这样的树就是如题所说的“对称”。 以上图为例： 以 左3 作为根结点做前序遍历（根、左、右）依次遍历是 3、4、9、7、5、6、2 （这些元素都在1为根节点左子树） 以 右3 作为根节点做“对称前序遍历”（根、右、左）依次遍历是 3、4、9、7、5、6、2 （这些元素都在1为根节点右子树） 可以看出如果对称的话 前序遍历 和 “对称前序遍历”（根、右、左）的结果是一样的(如果单单是先序遍历，然后对比该结点是不够的，因为先序遍历确定后，树的形状也可能是不同，故而还需要比较当前结点的左右结点情况） 从而也可以利用中序遍历（左、根、右）和“对称中序遍历”（右、根、左）或后序遍历（左、右、根）和“对称后序遍历”（右、左、根）来解这道题
2、具体实现 将一棵树同时采用对称的深度搜索。即比较节点值是否相等，如果相等再比较左边节点的左子树和右边节点的右子树是否对称，如果对称再比较左边界点的右子树和右边节点的左子树是否对称。最终返回值就是正确答案。
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isSymmetric(TreeNode* root) { return check(root, root); } bool check(TreeNode *x, TreeNode *y) { if(x == nullptr && y == nullptr) return true; if((x == nullptr && y != nullptr) || (x != nullptr && y == nullptr)) return false; return x->val == y->val && check(x->left, y->right) && check(x->right, y->left); } };二、迭代的方法：采用广度优先遍历来解决问题，每一层的值都是对称的那么树就是对称的。 代码略。
