题解 | #对称的二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
 //方法：递归（二叉树大部分问题都是用递归解决）
 //思路：
    //特殊：根节点不用比较，需要比较的根节点的左右孩子，
    //接下来比较的左孩子的左孩子节点与右孩子的右孩子节点，左孩子的右孩子节点与右孩子的左孩子节点，递归下去
//递归出口：两个节点同时为空或者两个节点相等

//步骤
//主函数：
    //1、判空树，空则返回true，否则进行下一步
    //2、调用局部函数判断左右子树是否相等，并返回其值
//局部函数
    //1、判断左右孩子是否为空，空着返回true，否则返回false
    //2、判断左右子树是是否相等，相等返回true,否则进行下一步
    //3、调用递归来判断（左孩子的左孩子节点与右孩子的右孩子节点，左孩子的右孩子节点与右孩子的左孩子节点是否都相等），相等返回true,否则若只有其中某一方为空，返回false

//局部函数:
int equal(struct TreeNode* lChild, struct TreeNode* rChild)
{
    //1、判断左右孩子是否为空，空着返回true，否则若只有其中某一方为空，返回false
    if(!lChild && !rChild)
    {
        return true;
    }
    else if ((!lChild && rChild) || (lChild && !rChild)) 
    {
        return false;
    }

    //2、判断左右子树是是否相等，相等返回true,否则进行下一步
    if(lChild->val == rChild->val)
    {
        if(equal(lChild->left, rChild->right) && equal(lChild->right, rChild->left))
            return true;
        else
            return false;
    }
    else 
        return false;

    //3、调用递归来判断（左孩子的左孩子节点与右孩子的右孩子节点，左孩子的右孩子节点与右孩子的左孩子节点是否都相等），相等返回true,否则返回false
}

//主函数：
bool isSymmetrical(struct TreeNode* pRoot )
 {
    // write code here
    //1、判空树，空则返回true，否则进行下一步
    if(!pRoot)
    {
        return true;
    }

    //2、调用局部函数判断左右子树是否相等，并返回其值
    return equal(pRoot ->left, pRoot->right);
}