# 题目

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

** 进阶：** 你可以运用递归和迭代两种方法解决这个问题吗？

# 分析

镜像对称，我们需要比较二叉树的外侧和内侧是否都相等

本题遍历只能是 “后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。

递归：

	class Solution {
	public:
	bool compare(TreeNode* left, TreeNode* right) {
	// 首先排除空节点的情况
	if (left == NULL && right != NULL) return false;
	else if (left != NULL && right == NULL) return false;
	else if (left == NULL && right == NULL) return true;
	// 排除了空节点，再排除数值不相同的情况
	else if (left->val != right->val) return false;

	// 此时就是：左右节点都不为空，且数值相同的情况
	// 此时才做递归，做下一层的判断
	bool outside = compare(left->left, right->right); // 左子树：左、右子树：右
	bool inside = compare(left->right, right->left); // 左子树：右、右子树：左
	bool isSame = outside && inside; // 左子树：中、右子树：中（逻辑处理）
	return isSame;

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

	}
	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;
	}

	// 左右一个节点不为空，或者都不为空但数值不相同，返回 false
	if ((!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;
	}
	};

二叉树