判断是不是对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

问题分析

解题思路1

/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
* 左子树的右子树和右子树的左子树相同即可，采用递归
* 非递归也可，采用栈或队列存取各级子树根节点
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == nullptr) {
            return true;
        }
        return comRoot(pRoot->left, pRoot->right);
    }
    bool comRoot(TreeNode* left, TreeNode* right) {
        // TODO Auto-generated method stub
        if (left == nullptr) return right == nullptr;
        if (right == nullptr) return false;
        if (left->val != right->val) return false;
        return comRoot(left->right, right->left) && comRoot(left->left, right->right);
    }
};

解题思路2

class Solution {
public:

    bool isLR(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (pRoot1 == nullptr  )
        {
            return pRoot2 == nullptr;
        }
        //注意条件
        if (pRoot2 == nullptr)
        {
            return false;
        }
        
        if (pRoot1->val != pRoot2->val)
        {
            return false;
        }
        bool res = isLR(pRoot1->left, pRoot2->right) && isLR(pRoot1->right, pRoot2->left);
        return res;
    }

    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == nullptr)
        {
            return true;
        }
        return isLR(pRoot->left,pRoot->right);
    }

};