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

两个方法：采用双端队列、采用递归

/**
 * 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
        // 法一：
        // return deque_Symmetric(root);

        // 法二：
        if(!root)
            return true;
        return isEqual(root->left, root->right);
    }

    // 采用deque结构来实现
    bool deque_Symmetric(TreeNode* root)
    {
        if((root && (root->left && !root->right)) || (root &&(!root->left && root->right)))
            return false;
        if(!root || (root && !root->left && !root->right))
            return true;
        deque<TreeNode*> deq;
        deq.push_front(root->left);
        deq.push_back(root->right);
        while(!deq.empty())
        {
            TreeNode* leftRoot = deq.front();
            TreeNode* rightRoot = deq.back();
            if(leftRoot->val != rightRoot->val)
                return false;
            deq.pop_front();
            deq.pop_back();
            if(leftRoot->left && rightRoot->right)
            {
                deq.push_front(leftRoot->left);
                deq.push_back(rightRoot->right);
            }
            if(leftRoot->right && rightRoot->left)
            {
                deq.push_front(leftRoot->right);
                deq.push_back(rightRoot->left);
            }
            if((leftRoot->left && !rightRoot->right) || (leftRoot->right && !rightRoot->left))
                return false;
        }
        return true;
    }

    // 法二：采用递归方法
    // 三部曲：
    // 1、确定函数的返回值和输入参数
    // 2、终止条件
    // 3、单层逻辑（这一次递归需要做什么）

    bool isEqual(TreeNode* rootLeft, TreeNode* rootRight)
    {
        // 终止条件
        if((rootLeft && !rootRight) || (!rootLeft && rootRight) || (rootLeft && rootRight && rootLeft->val != rootRight->val))
            return false;
        else if(!rootLeft && !rootRight)
            return true;
        return isEqual(rootLeft->left, rootRight->right) && isEqual(rootLeft->right, rootRight->left);
    }


};