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

理解何为对称
如下图所示，以根节点做中轴，沿着中轴线翻转，左边的子树结构与右边完全一样，并且对应的每一个节点得都一样

可以同过left、right两个指针在树上移动，模拟判断树是否对称；

题解一:递归
主要思路：使用递归函数，在递归函数里面传入两个指针，充当上图中得left、right指针；
思考点：
递归函数返回值：
是：true，不是：false

递归函数的停止条件：
1、left、right指针指向的节点必须同时为空，返回true
2、left、right指针指向的节点不同时为空，返回false
3、left、right指针指向的节点都不为空，值不相同，返回false；
4、left、right指针指向的节点都不为空，值相同，递归调用下一层，判断是否上足上述3点要求；

从上图模拟中可以看出我们的递归调用方案：
判断下一层是否满足对称时，传入的left、right指针不在同一侧，即 f(Lroot->left,Rroot->right)和 f(Lroot->right,Rroot->left)

复杂度分析：
时间复杂度:O(n),n为二叉树的节点
空间复杂度:O(n),递归栈深度

实现如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool f(TreeNode* Lroot, TreeNode* Rroot) {
    if (!Lroot && !Rroot)return true;//left、right指针指向的节点必须同时为空，返回true
    if (!Lroot || !Rroot)return false;//left、right指针指向的节点不同时为空，返回false
    if (Lroot->val != Rroot->val)return false;//left、right指针指向的节点都不为空，值不相同，返回false；
    return f(Lroot->left, Rroot->right) && f(Lroot->right, Rroot->left);//left、right指针指向的节点都不为空，值相同，递归调用下一层，判断是否上足上述3点要求；

}

bool isSymmetric(TreeNode* root) {
    // write code here
    return f(root, root);
}
};

题解二：利用队列
主要思路：
1、将left、right指针指向对称的两个节点值存入队列，如果树结构不一致，直接返回fale，将一层的对称的节点值相邻存放至队列中；
参照上图模拟情况的四个步骤，队列中的存放元素如下图所示（根节点特判单独处理）：

2、每次从队列中取两个值，判断是否相等，以此来判断是否对称；
3、遍历完所有的节点，全都符合对称定义，即返回true，否则返回false；

复杂度分析：
时间复杂度:O(n),n为二叉树的节点

实现如下：

/**
 * 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;//特判根节点；
        queue<TreeNode*> q;
        q.push(root->left);   // 将左子树头结点加入队列
        q.push(root->right);  // 将右子树头结点加入队列
        while (!q.empty()) {  // 接下来就要判断这这两个树是否相互翻转
            TreeNode* leftNode = q.front(); 
            q.pop();//出队    
            TreeNode* rightNode = q.front(); 
            q.pop();//出队
            if (!leftNode && !rightNode) {  //left、right指针指向的节点同时为空，满足对称条件
                continue;
            }
            //left、right指针指向的节点不同时为空或者left、right指针指向的节点都不为空，值不相同，直接返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { 
                return false;
            }
            //将相互对称的节点放在相邻的位置
            //从逻辑上看，将下一层的对称的节点放在一起；
            q.push(leftNode->left);   // 加入左节点左孩子
            q.push(rightNode->right); // 加入右节点右孩子
            q.push(leftNode->right);  // 加入左节点右孩子
            q.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

题解三：利用栈
思路与题解二差不多，但是逻辑上类似于深度搜索，将两个字节的对称路径上的节点判断是否值相等；
实现如下：

/**
 * 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*> s;
        s.push(root->left);   // 将左子树头结点加入栈
        s.push(root->right);  // 将右子树头结点加入栈
        while (!s.empty()) {  // 接下来就要判断这这两个树是否相互翻转
            TreeNode* leftNode = s.top(); 
            s.pop();//出栈    
            TreeNode* rightNode = s.top(); 
            s.pop();//出栈
            if (!leftNode && !rightNode) {  //left、right指针指向的节点同时为空，满足对称条件
                continue;
            }
            //left、right指针指向的节点不同时为空或者left、right指针指向的节点都不为空，值不相同，直接返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { 
                return false;
            }
            //将相互对称的节点放在相邻的位置
            s.push(leftNode->left);   // 加入左节点左孩子
            s.push(rightNode->right); // 加入右节点右孩子
            s.push(leftNode->right);  // 加入左节点右孩子
            s.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};