题解 | #判断二叉树是否对称#

题目：判断二叉树是否对称

描述：给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的

下面这棵二叉树不对称。

备注：希望你可以用递归和迭代两种方法解决这个问题

示例1：输入：{1,2,2}，返回值：true

解法一：

思路分析：对称的二叉树是关于以根节点为一条直线对称的，主要分为几种情况：

一：左子树存在，而右子树不存在，直接返回false；

二：左子树不存在，右子树存在，直接返回false；

三：左右子树都不存在直接返回true；

四：根节点root的左子树的值不等于根节点右子树的值，直接返回false；

五：当根节点root的左子树的值等于根节点右子树的值时，此时需要做进一步递归处理，分别判断，左子树的左是否等于右子树的右，左子树的右是否等于右子树的左。

实例分析：输入{1，2，2，3，4，4，3}，下面使用表进行分析。

具体C++代码如下所示：

#include<stdbool.h>
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool com(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 = com(left->left, right->right);// 左子树：左、 右子树：右
        bool inside = com(left->right, right->left);// 左子树：右、 右子树：左
        bool Same = outside && inside;
        return Same;
 
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return com(root->left, root->right);
    }
};

递归遍历每一个元素值，判断两个元素值是否相等，为O(N/2)，所以时间复杂度为O(N)，空间复杂度为O(1)。

解法二：
思路分析：其实，在进行解法一的运算后，我们发现，在使用递归进行判断的同时，也可以直接使用队列或者栈的运算，将二叉树要比较的元素按照顺序放入容器当中，然后取出来成对的进行比较，下面我们使用栈进行判断。

实例分析：输入{1，2，2，3，4，4，3}

首先判断root的值，同时设定一个stack栈对象，将root的左子树与右子树的值放进stack栈对象中，然后进行判断，如果不相等，直接返回false，如果相等，递归判断解法一的前四条语句，满足，即可返回true。

具体C++代码如下所示：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        // write code here
        if(root == NULL)
            return true;
        stack<TreeNode*> tree;
        tree.push(root->left);//将左子树送入
        tree.push(root->right); //将右子树存入
        while(!tree.empty()){
            TreeNode* left = tree.top();//左子树为第一个
            tree.pop();
            TreeNode* right = tree.top(); //右子树为第二个
            tree.pop();
            //判断
            if(!left && !right)
                continue;
            if(!left || !right || (left->val != right->val)){
                return false;
            }
            tree.push(left->left);//将左子树放进去
            tree.push(right->right);//与右子树的右子树作比较
            tree.push(left->right);//同上
            tree.push(right->left);
        }
        return true;
    }
};

最快所需的时间是root的左子树不等于root的右子树，直接返回false，最慢是最后一层二叉树判断完成。平均时间复杂度为O(N)，空间复杂度为O(N)。