101. 对称二叉树（剑指 Offer 28. 对称的二叉树）（简单）

题目链接：101. 对称二叉树
题目基础：102. 二叉树的层序遍历
相同题目：剑指 Offer 28. 对称的二叉树

思路一：补全儿子结点
给每个节点都补全左右儿子结点（如果没有的话），补的值为INT_MIN
之后用vector嵌套容器存储
再用双指针遍历每一层的第一个和倒数第一个，第二个和倒数第二个。。。值是否相等

此代码是在102. 二叉树的层序遍历基础上改的，方法为广度优先遍历

class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		vector> v;
		if (!root) {
			return true;
		}

		queue q;
		q.push(root);

		while (!q.empty()) {
			int current_level_size = q.size();
			v.push_back(vector());

			for (int i = 1; i <= current_level_size; i++) {
				auto node = q.front();
				q.pop();
				if (node) {
					v.back().push_back(node->val);
				}
				else {
					v.back().push_back(INT_MIN);
					continue;
				}

				if (node->left) {
					q.push(node->left);
				}
				else {
					q.push(nullptr);
				}

				if (node->right) {
					q.push(node->right);
				}
				else {
					q.push(nullptr);
				}
			}
		}

		for (int i = 1; i < v.size(); i++) {
			int n = v[i].size();   //每一层元素的个数
			int left = 0;
			int right = n - 1;
			for (left; left < n / 2; left++) {
				if (v[i][left] == v[i][right]) {
					right--;
				}
				else {
					return false;
				}
			}
		}

		return true;
	}
};

思路二：
正经的迭代法如下：

树的根结点不需要加入栈，我们直接把左子树和右子树入栈

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue 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;
    }
};

改的能看懂：

class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		if (root == nullptr) return true;

		queue q;
		q.push(root->left);
		q.push(root->right);

		while (!q.empty()) {
			auto leftNode = q.front(); q.pop();
			auto rightNode = q.front(); q.pop();

			//某结点的左右结点为空  说明对称的
			if (leftNode == nullptr && rightNode == nullptr) continue;
			
			//一个为空一个不为空  或者val不相等  则非对称
			if (leftNode == nullptr && rightNode != nullptr) return false;
			if (leftNode != nullptr && rightNode == nullptr) return false;
			if (leftNode->val != rightNode->val) return false;

			q.push(leftNode->left);
			q.push(rightNode->right);
			q.push(rightNode->left);
			q.push(leftNode->right);
		}

		return true;
	}
};

思路三：递归
链接
递归的思路可以看上面的链接，比官方答案要清晰很多

递归三部曲：
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑

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