题目描述

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

** 题解:递归**

注意：
1、对于需要比较节点中的值的时候，需要提前判断节点是否为空；
2、如果不需要比较节点的值，那么递归调用时候不需要提前判断节点是否为空；
3、如果是需要有两个节点进行比较，那么需要创建一个递归函数；
递归函数中，通常先进性比较，然后分别进行左子树和右子树的递归
4、如果不需要两个节点进行比较，不需要重新创建递归函数，以本函数作为递归函数。

代码

/*
	描述
	给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
*/
/*
    题解1：递归
    注意：
    1、对于需要比较节点中的值的时候，需要提前判断节点是否为空；
    2、如果不需要比较节点的值，那么递归调用时候不需要提前判断节点是否为空；
    3、如果是需要有两个节点进行比较，那么需要创建一个递归函数；
     递归函数中，通常先进性比较，然后分别进行左子树和右子树的递归
    4、如果不需要两个节点进行比较，不需要重新创建递归函数，以本函数作为递归函数。
*/
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL) {
    }
};
bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
    //递归出口
    if (!pRoot1 && !pRoot2) //两个节点都为空时，返回真
        return true;
    if (!pRoot1 || !pRoot2)//两个节点都存在空节点时，返回假
        return false;
    //if(pRoot1->val ==pRoot2->val){
    //    return isSame(pRoot1->left,pRoot2->right) &&
    //           isSame(pRoot1->right,pRoot2->left);            
    //}else
    //    return false;

    //上面几行加了注释的代码也可以用下面几行代码表示
    if (pRoot1->val != pRoot2->val) return false;
    if (isSame(pRoot1->left, pRoot2->right) && isSame(pRoot1->right, pRoot2->left))
        return true;
    return false;
}
bool isSymmetrical(TreeNode* pRoot) {
    if (!pRoot)
        return true;
    return isSame(pRoot->left, pRoot->right);
    //注意：这里不能再此处进行自我递归，因为形参只有一个
    //若自我递归，得到的是子树左右结点的比较，而不是左子树的左节点和右子树的右节点比较。
    //所以只能再递归函数中进行递归。
}